FREQUENCY ESTIMATES FOR LINEAR EXTENSION MAJORITY CYCLES ON PARTIAL ORDERS

A linear order L on a set X is a linear extension of partial order P on X if P subset-or-equal-to L. L (P) denotes the set of all linear extensions of P, and L (x, y) denotes the subset of L (P) for which xL(i))y if L(i) is-an-element-of L (x, y). A linear extension majority (LEM) relation M is defined by xMy if # L (x, y) > # L (y, x). A LEM cycle exists on P if xMy, yMz and zMx for some x, y, z is-an-element-of X. Similarly M' on X is defined by xM'y if # L (x, y) greater-than-or-equal-to # L (y, x) for x not-equal y. A LEM quasi-cycle exists if xM'y, yM'z and zM'x for some x, y, z is-an-element-of X and the equality part of the M' definition holds for exactly one of the pairs in the triple. A Monte-Carlo simulation study is conducted to obtain estimates of the relative freqency with which LEM cycles and LEM quasi-cycles are observed.