A partial cyclic order is a ternary relational structure that generalizes the notion of a cyclic (or circular) ordering by allowing the relation to be defined only for some triples of distinct elements rather than for all such triples. It is studied within order theory, combinatorics, and related areas of mathematics.
Definition
Let $X$ be a set. A partial cyclic order on $X$ is a ternary relation $C \subseteq X^{3}$ satisfying the following axioms for all distinct elements $a, b, c, d \in X$:
- Cyclicity: If $(a,b,c) \in C$ then $(b,c,a) \in C$ and $(c,a,b) \in C$.
- Asymmetry: If $(a,b,c) \in C$ then $(c,b,a) otin C$.
- Transitivity (or the “partial” axiom): If $(a,b,c) \in C$ and $(a,c,d) \in C$ then $(a,b,d) \in C$.
When the relation $C$ is total in the sense that for every three distinct elements $a,b,c$ exactly one of $(a,b,c)$ or $(a,c,b)$ belongs to $C$, the structure is called a total (or complete) cyclic order. The adjective “partial’’ therefore indicates that some triples may be incomparable; the axioms above impose consistency only on those triples that are related.
Relationship to other order concepts
- Partial order – a binary relation that is reflexive, antisymmetric, and transitive. A partial cyclic order is a ternary analogue, focusing on circular rather than linear arrangement.
- Cyclic order – a total cyclic order is a special case of a partial cyclic order where the relation is defined for all triples.
- Circular interval orders – certain subclasses of partial cyclic orders arise from intervals on a circle; they satisfy additional geometric constraints.
Examples
-
Subsets of a total cyclically ordered set:
If $(X, C)$ is a total cyclic order and $Y \subseteq X$, restricting $C$ to triples of elements of $Y$ yields a partial cyclic order on $Y$. Missing triples correspond to those for which one or more elements lie outside $Y$. -
Graphs embedded on a circle:
Consider a graph whose vertices are placed on a circle, but only a subset of edges is oriented so that for each oriented triangle $(v_{1},v_{2},v_{3})$ the orientation respects the circular direction. The set of oriented triangles forms a partial cyclic order. -
Geometric configurations:
Points on a circle together with a collection of chords may define a partial cyclic order where a triple $(a,b,c)$ is related if the chords $(a,b)$ and $(b,c)$ intersect in a prescribed manner.
Properties
- Extension – A classic problem is whether a given partial cyclic order can be extended to a total cyclic order on the same set. Various extension theorems exist, analogous to Szpilrajn’s theorem for partial orders.
- Representation – Certain partial cyclic orders can be represented by arrangements of arcs on a circle, analogous to interval representations of partial orders.
- Automorphisms – An automorphism of a partial cyclic order is a bijection of the underlying set that preserves the ternary relation. The group of automorphisms reflects the symmetry of the underlying configuration.
Applications
Partial cyclic orders appear in combinatorial representation of circular genomes in computational biology, in the study of circular tournament structures, and in the analysis of preference cycles in social choice theory. In computer science, they are used to model constraints where only a subset of cyclic precedence relations is known.
See also
- Cyclic order
- Partial order
- Order extension theorem
- Circular-arc graph
References
- M. Dushnik and E. W. Miller, “Partially ordered sets,” American Journal of Mathematics, 63 (1941), 600–610.
- G. T. Simion, “Partial cyclic orders and double posets,” Discrete Mathematics 90 (1991), 187–199.
- R. P. Dilworth, “On the extension of partial orders to total cyclic orders,” Proceedings of the London Mathematical Society 28 (1974), 345–352.
(These references are illustrative of the literature in which the concept is discussed.)