Colexicographical order

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.

Suppose

$\{ A_1, A_2, \ldots, A_n \}$

is an n-tuple of sets, with respective total orderings

$\{ <_1, <_2, \ldots, <_n \}$

The colex ordering

$\ \ <^\text{colex}$

of

$A_1 \times A_2 \times \cdots \times A_n$

is then

$(a_1, a_2, \dots, a_n) <^\text{colex} (b_1,b_2, \dots, b_n) \iff (\exists\ m > 0) \ (\forall\ i > m) (a_i = b_i) \land (a_m <_m b_m)$

The following is an ordering on the 3-element subsets of $\{1,2,3,4,5,6\}$, 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

Orderings of the 3-subsets of $\scriptstyle \{1,...,6\}$ (and the corresponding binary vectors) Colex order is in the bottom right corner.

Orderings of the 24 permutations of $\scriptstyle \{1,...,5\} \,$ that have a complete 5-cycle The inversion vectors of permutations in colex order are in revcolex order, and vice versa.

External links

• Lexicographic and colexicographic order

Colexicographic order in the OEIS-Wiki