Colexicographical order

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 aa′).

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 subsets of size 3 from the set {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

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Lexicographical order — In mathematics, the lexicographic or lexicographical order, (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product), is a generalization of the way the alphabetical order of words is based on the… …   Wikipedia

  • Kruskal–Katona theorem — The Kruskal ndash;Katona theorem is a combinatorial theorem about uniform hypergraphs. It can be used to derive facts about abstract simplicial complexes. It is named for Joseph Kruskal and Gyula O. H. Katona.For an n element set X , define the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”