Cyclic order
|
In 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.
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.
It can be instinctive to use cyclic orders for symmetric functions, for example as in
- <math> xy + yz + zx<math>
where writing the final monomial as <math>xz<math> 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.