Ordre cyclique

Sur un ensemble donné, un ordre cyclique est une relation ternaire R :

• cyclique, c'est-à-dire invariante par permutation circulaire : R(x, y, z) ⇒ R(y, z, x) ;
• asymétrique : R(x, y, z) ⇒ ¬R(z, y, x) ;
• transitive : R(x, y, z) et R(x, z, u) ⇒ R(x, y, u)[1].

Un ordre cyclique R est dit total s'il est de plus

• complet : x, y, z distincts ⇒ R(u, v, w) pour au moins l'un des six permutés (u, v, w) de (x, y, z),

donc pour exactement trois permutés : ou bien (x, y, z) et ses permutés circulaires, ou bien (x, z, y) et ses permutés circulaires[1].

En présence de la cyclicité et de la transitivité, l'asymétrie équivaut à la condition d'antiréflexivité[2] : ¬R(x, x, y).

En effet :

• la donnée d'une relation ternaire R équivaut à celle de la famille des relations binairesR_x = R(x, ∙, ∙) ;
• si la relation ternaire R est cyclique, alors elle est :
  • asymétrique si et seulement si chaque R_x est une relation (binaire) asymétrique : R_x(y, z) ⇒ ¬R_x(z, y),
  • transitive si et seulement si chaque R_x est une relation (binaire) transitive : R_x(y, z) et R_x(z, u) ⇒ R_x(y, u),
  • antiréflexive si et seulement si chaque R_x est une relation (binaire) antiréflexive : ¬R_x(y, y).

Or toute relation binaire asymétrique est antiréflexive, et toute relation binaire transitive et antiréflexive — c'est-à-dire tout ordre strict — est asymétrique.

En résumé :

• Un ordre cyclique est une relation ternaire cyclique R dont les relations binaires R_x associées sont des ordres stricts.
• Un ordre cyclique total — ou ordre cyclique complet, ou cycle — est une relation ternaire cyclique R dont les relations binaires R_x associées sont des ordres stricts totaux.

Le problème de la complétion des ordres cycliques contraste fortement avec celui des ordres usuels. Pour ces derniers, le théorème d'extension de Szpilrajn garantit que tout ordre partiel sur un ensemble E — fini ou infini — est prolongeable en un ordre total sur E, et dans le cas où E est fini, on dispose d'algorithmes linéaires qui fournissent un tel prolongement. Les ordres cycliques même finis, au contraire, ne sont pas toujours prolongeables en des ordres cycliques complets, et le problème de décision correspondant est NP-complet, car 3-SAT s'y réduit[3].

• Roland Fraïssé, « L'intervalle en théorie des relations ; ses généralisations, filtre intervallaire et clôture d'une relation », dans M. Pouzet et D. Richard, Orders: Descriptions and Roles, North-Holland, coll. « Annals of Discrete Mathematics » (n^o 23), 1984 (lire en ligne), p. 313-342
• (en) Nimrod Megiddo, « Partial and complete cyclic orders », Bull. Amer. Math. Soc., vol. 82, n^o 2,‎ 1976, p. 274-276 (lire en ligne)

• Portail des mathématiques