In mathematics, the colexicographic or colex order, is a natural order structure of the Cartesian product of two or more ordered sets. It is similar in structure to the lexicographical order. Colexicographical ordering is used in the Kruskal-Katona theorem.
Given two partially ordered sets A and B, the colexicographical order on the Cartesian product A × B is defined as
- (a,b) ≤ (a′,b′) if and only if b < b′ or (b = b′ and a ≤ a′).
The result is a partial order. If A and B are totally ordered, then the result is a total order also.
More generally, one can define the colexicographic order on the Cartesian product of n ordered sets.
is an n-tuple of sets, with respective total orderings
The colex ordering
The following is an ordering on the 3-element subsets of , based on the colex ordering of the triples obtained by writing the elements of each subset in ascending order:
- 123 < 124 < 134 < 234 < 125 < 135 < 235 < 145 < 245 < 345 < 126 < 136 < 236 < 146 < 246 < 346 < 156 < 256 < 356 < 456