Partial and complete cyclic orders
Nimrod Megiddo · Bulletin of the American Mathematical Society · 1976
We show that, in contrast to a famous theorem on linear orders, not every partial cyclic order on M = {1, . . ., m} can be extended to a complete cyclic order.In fact, the complexity, in a certain sense, of sufficient conditions for such an extendability increases rapidly with m.DEFINITION 1. (i) Two linear orders, (a t , . . ., a m ) and (b x , . . ., b m ), on M are called cyclically equivalent if there exists k G M such that [ ƒ -1 = (i -1 4-k) (mod m)] =» a t = bj.(ii) A complete cyclic order (CCO) on M is an equivalence class C of linear orders modulo cyclic equivalence; denote a x a 2 • • • a m for the equivalence class containing (a x , a 2 , . . ., a m ).DEFINITION 2. A partial cyclic order (PCO) on M is a set A of cyclically ordered triples (COTs) out of M such that:(iTHEOREM 3. (i) If C is a CCO then the set A of all COTs derived from C is a PCO.(ii) If A is a saturated PCO, i.e., {x, y, z} G (^) & xyz € A =» zyx G A, then there exists a CCO from which all of A's COTs are derived', A is then said to be extendable to a CCO.COROLLARY 4. A PCO is extendable to a CCO if and only if it is contained in a saturated PCO.It is natural to ask whether every PCO is extendable to a CCO (or, equiva-lent^, is contained in a saturated PCO).In view of the following example, the answer is in the negative.EXAMPLE 5. Let M = {a, b, . . ., m} be the set of the first thirteen letters, and let A = {acd, bde, cef dfg, egh, fha, gac, hcb, abi, ci], bjk, ikl, jlm, kma, lab, mbc, hem, bhm).Obviously, A is a PCO.Suppose that A* D A is a saturated PCO.If abc G A* then, since acd G A*, also bed G A*.Then, also cde G A*, and successive applications of transivity finally yield acb G A*, which contra-AMS (MOS) subject classifications (1970).Primary 05B99, 06A05, 06A10; Secondary 05C35, 68A20.