Linear extension majority cycles on partial orders

Let P define a partial order on a set X of cardinalityn. A linear extensionL ofP is a linear order withP G L, and is the set of all linear extensions ofP. denotes that subset of withxLy forx, y X. A linear extension majority (LEM) relationM onX is defined byxMy if . Similarly,M is defined byxMy if . An LEM cycle exists if there arex, y, z X withxMyMzMx, and an LEM quasi-cycle exists ifxMyMzMx and the equality part of the definition ofM holds for exactly one pair in the triple. The study shows that no semiorders have LEM cycles or LEM quasi-cycles, and that every interval order has a maximal element under theM relation. LEM cycles and LEM quasi-cycles are also considered for partial orders with specific structures. Simulation is used to determine the relative likelihood with which LEM cycles and LEM quasi-cycles are observed when connected partial orders are generated at random by a specific procedure.Dr. Gehrlein's research was supported through a fellowship from the Center for Advanced Study of the University of Delaware.