×

Cyclic orders. (English) Zbl 0692.05059

Summary: A family F of triplets of a set X is a cyclic order if the following axioms are satisfied: \[ \begin{alignedat}{2} (a,b,c)\in F &\Rightarrow (b,c,a) \text{ and }(c,a,b)\in F &&\text{(cyclicity);}\\ (a,b,c)\in F &\Rightarrow (b,a,c)\not\in F &&\text{(antisymmetry);}\\ (a,b,c) \text{ and }(c,d,a)\in F &\Rightarrow (b,c,d) \text{ and }(d,a,b)\in F &&\text{(transitivity).} \end{alignedat} \] Such a concept aims to formalize some problems related to points or intervals drawn on a circle or on the plane, or with geometric representations of finite groups (\((a,b,c)\in F\) is to be read as ‘\(b\) is located between \(a\) and \(c\)’).
We move into the context of the so defined ternary relation some classical questions arising in the theory of partial ordered subsets, and deal, for instance, with extendability problem and with the problem of the minimal partition of a cyclic order into complete cyclic suborders. We also present several applications to such questions as the characterization of cyclic graphs or circular-arc graphs.

MSC:

05C99 Graph theory
06A06 Partial orders, general
Full Text: DOI

References:

[1] Alles, P.; Nesetril, J.; Poljak, S., Extendability, dimension and cyclic orders (1985), Technische Hochschule: Technische Hochschule Darmstadt, Preprint 944
[2] Berge, C., Graphes et Hypergraphes (1974), Dunod: Dunod Paris, Ch. 16 · Zbl 0213.25702
[3] Dilworth, R., A decomposition theorem for partially ordered sets, Ann. Math. (2), 51, 161-166 (1951) · Zbl 0038.02003
[4] Dushnik, B.; Miller, E., Partially ordered sets, Am. J. Math., 63, 600-610 (1941) · JFM 67.0157.01
[5] Fournier, J., Une caracterisation des graphes de cordes, C. R. Acad. Sci., Paris, 286A, 81-83 (1978) · Zbl 0378.05045
[6] Gallil, Z.; Meggido, N., Cyclic ordering is NP-complete, Theoret. Comput. Sci., 5, 79-82 (1977)
[7] Heyting, A., Axiomative Projective Theory (1963), Academic Press: Academic Press New York
[8] Huntington, E., A set of completely independent postulates for cyclic orders, Proc. Nat. Acad. Sci. U.S.A., 10, 630-631 (1924)
[9] Lovacz, L., Normal hypergraphs and the perfect graphs conjecture, Discr. Math., 2, 253-267 (1972) · Zbl 0239.05111
[10] Muller, G., Lineare and zyklische ordnung, Praxis Math., 16, 261-269 (1974) · Zbl 0369.06001
[11] Naji, W., Reconnaissance des graphes de cordes, Discr. Math., 54, 329-337 (1985) · Zbl 0567.05033
[12] Novak, V.; Novotny, M., On determination of a cyclic order, Czech Math. J., 33, 555-563 (1983) · Zbl 0537.06004
[13] Papadimitriou, C.; Stiegler, K., Combinatorial Optimization Algorithms and Their Complexity (1982), Prentice-Hall, Ch. 3 and 6 · Zbl 0503.90060
[14] Quilliot, A., A circular representation problem, Discr. Math., 5, 251-264 (1984) · Zbl 0548.05047
[15] Read, R., The chord intersection problem, Ann. N.Y. Acad. Sci., 319, 444-454 (1979) · Zbl 0479.05005
[16] Redei, L., Begrundung der euklidischen geometrien, Budapest (1965) · Zbl 0136.14901
[17] Rotman, J., The Theory of Groups (1970), Allyn and Bacon: Allyn and Bacon Boston · Zbl 0207.21401
[18] Trotter, T.; Moore, J., Characterization theorems for graphs, posets, lattices and families of sets, Discr. Math., 16, 36-38 (1976)
[19] Tucker, A., Structure theorems for some circular arc graphs, Discr. Math., 7, 167-195 (1974) · Zbl 0269.05119
[20] Tucker, A., Coloring a family of circular arc graphs, SIAM J. Appl. Math., 29, 493-502 (1975) · Zbl 0312.05105
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.