Colexicographical order
Encyclopedia
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 set
s A and B, the colexicographical order on the Cartesian product A × B is defined as ≤ (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
is an n-tuple of sets, with respective total orderings
The colex ordering
of
is then
The following is an ordering on subsets of size 3 from the set
, based on the colex ordering of the triples obtained by writing the elements of each subset in ascending order:
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the colexicographic or colex order, is a natural order
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
structure of the Cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
of two or more ordered sets. It is similar in structure to the lexicographical order
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
. Colexicographical ordering is used in the Kruskal-Katona theorem.
Given two partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
s A and B, the colexicographical order on the Cartesian product A × B is defined as ≤ (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
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
, 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
is an n-tuple of sets, with respective total orderings
The colex ordering
of
is then
The following is an ordering on subsets of size 3 from the set
, 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