Misplaced Pages

Partial cyclic order

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
You can help expand this article with text translated from the corresponding article in French. (November 2019) Click for important translation instructions.
  • Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Misplaced Pages.
  • Consider adding a topic to this template: there are already 1,687 articles in the main category, and specifying|topic= will aid in categorization.
  • Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article.
  • You must provide copyright attribution in the edit summary accompanying your translation by providing an interlanguage link to the source of your translation. A model attribution edit summary is Content in this edit is translated from the existing French Misplaced Pages article at ]; see its history for attribution.
  • You may also add the template {{Translated|fr|Ordre cyclique}} to the talk page.
  • For more guidance, see Misplaced Pages:Translation.

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.

Definition

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

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

Constructions

Direct sum

Direct product

Power

Dedekind–MacNeille completion

Extensions

linear extension, Szpilrajn extension theorem

standard example

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, cyclic ordering is NP-complete, since it solves 3SAT. This is in stark contrast with the recognition problem for linear orders, which can be solved in linear time.

Notes

  1. Novák 1982.
  2. Novák & Novotný 1984a.
  3. Novák & Novotný 1984b.
  4. Megiddo 1976, pp. 274–275.
  5. Megiddo 1976, pp. 275–276.
  6. Galil & Megiddo 1977, p. 179.

References

Further reading

Categories: