Cyclic order
Encyclopedia
|
| Tutorials | Encyclopedia | Dictionary | Directory |
|
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
for all x, y, z, w in X. It can be instinctive to use cyclic orders for symmetric functions, for example as in
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
|
|
top
©2008-2009 TutorGig.com. All Rights Reserved. Privacy Statement