Search: in
Cyclic order
Cyclic order Encyclopedia
  Tutorials     Encyclopedia     Dictionary     Directory  
Cyclic_order Email this to a friend      Cyclic_order


Cyclic order

In combinatorial mathematics, a cyclic order on a set X with n elements is an arrangement of X as on a clock face, for an n-hour clock. That is, rather than an order relation on X, we define on X just functions 'element immediately before' and 'element immediately following' any given x, in such a way that taking predecessors, or successors, cycles once through the elements as x(1), x(2), ..., x(n). Another way to put it is to say that we make X into the standard n-cycle directed graph on n vertices, by some matching of elements to vertices. A popular example is Rock, Paper, Scissors.

Any such cyclic ordering corresponds to n different total orders on X, considered as 'biting their tails'. There are therefore (n − 1)! cyclic orders on X.

An infinite set can also be ordered cyclically. The basic idea is the same: we arrange elements of the set around a circle. However, in the infinite case we cannot use the immediate successor relation; instead we use a ternary relation denoting that elements x, y, z occur after each other (not necessarily immediately) as we go around the circle. The general definition is as follows: a cyclic order on a set X is a relation R\subseteq X^3 such that

  1. R(x, y, z) implies R(y, z, x)
  2. not R(x, y, y)
  3. if x ? y ? z ? x, then R(x, y, z) or R(x, z, y)
  4. if R(x, y, z) and R(x, z, w), then R(x, y, w)

for all x, y, z, w in X.

It can be instinctive to use cyclic orders for symmetric functions, for example as in

xy + yz + zx\,

where writing the final monomial as xz would distract from the pattern.

A substantial use of cyclic orders is in the determination of the conjugacy classes of free groups. Two elements g and h of the free group F on a set Y are conjugate if and only if, when they are written as products of elements y and y-1 with y in Y, and then those products are put in cyclic order, the cyclic orders are equivalent under the rewriting rules that allow one to remove or add adjacent y and y−1.





Source: Wikipedia | The above article is available under the GNU FDL. | Edit this article


Search for Cyclic order in Tutorials
Search for Cyclic order in Encyclopedia
Search for Cyclic order in Dictionary
Search for Cyclic order in Open Directory
Search for Cyclic order in Store
Search for Cyclic order in PriceGig


Help build the largest human-edited directory on the web.
Submit a Site - Open Directory Project - Become an Editor

Advertisement

Advertisement



Cyclic order
Cyclic_order top Cyclic_order

Home - Add TutorGig to Your Site - Disclaimer

©2008-2009 TutorGig.com. All Rights Reserved. Privacy Statement