Partial cyclic order

In mathematics, a partial cyclic order is a ternary relation that generalizes a cyclic order in the same way that a partial order generalizes a linear order.

Over a given set, a partial cyclic order is a ternary relation ${\displaystyle R}$ that is:

• cyclic, i.e. it is invariant under a cyclic permutation: ${\displaystyle R(x,y,z)\Rightarrow R(y,z,x)}$
• asymmetric: ${\displaystyle R(x,y,z)\Rightarrow \not R(z,y,x)}$
• transitive: ${\displaystyle R(x,y,z)}$ and ${\displaystyle R(x,z,u)\Rightarrow R(x,y,u)}$¹

Various constructions of partial cyclic orders have been studied, analogous to constructions of other mathematical structures. These include the direct sum, the direct product, the power²³, and the Dedekind–MacNeille completion of a set.

The relationship between partial and total cyclic orders is more complex than the relationship between partial and total linear orders. To begin with, not every partial cyclic order can be extended to a total cyclic order. An example is the following relation on the first thirteen letters of the alphabet: {acd, bde, cef, dfg, egh, fha, gac, hcb} ∪ {abi, cij, bjk, ikl, jlm, kma, lab, mbc}. This relation is a partial cyclic order, but it cannot be extended with either abc or cba; either attempt would result in a contradiction.⁴

The above was a relatively mild example. One can also construct partial cyclic orders with higher-order obstructions such that, for example, any 15 triples can be added but the 16th cannot. In fact, determining whether a general ternary relation (or indeed a partial cyclic order)⁵ extends to a total cyclic order is NP-complete, since it solves 3SAT. This is in stark contrast with the problem to recognize when a binary relation extends to a linear order, which can be solved in linear time.⁶⁷ (In particular, every poset has a linear extension, even if it is infinite, by the Szpilrajn extension theorem.)

Several authors have considered the question of how complicated a non-extendable partial cyclic order must be. It is known that any partial cyclic order on 6 elements or fewer does extend to a total order. There is a single example (up to isomorphism) on 7 elements, which is constructed by adjoining an extra "point at infinity" to the standard example poset of dimension 3.⁸