In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order. Dushnik & Miller (1941) first studied order dimension; for a more detailed treatment of this subject than provided here, see Trotter (1992).
Formal definition The order dimension of a poset P {\displaystyle P} is the least integer t {\displaystyle t} for which there exists a family
R = ( < 1 , … , < t ) {\displaystyle {\mathcal {R}}=(<_{1},\dots ,<_{t})}
of linear extensions of P {\displaystyle P} so that, for every x {\displaystyle x} and y {\displaystyle y} in P {\displaystyle P} , x {\displaystyle x} precedes y {\displaystyle y} in P {\displaystyle P} if and only if it precedes y {\displaystyle y} in all of the linear extensions, if any such t {\displaystyle t} exists. In other words, that the intersection of those linear extensions equals P {\displaystyle P} . That is,
P = ⋂ R = ⋂ i = 1 t < i . {\displaystyle P=\bigcap {\mathcal {R}}=\bigcap _{i=1}^{t}<_{i}.}
An alternative definition of order dimension is the minimal number of total orders such that P embeds into their product with componentwise ordering i.e. x ≤ y {\displaystyle x\leq y} if and only if x i ≤ y i {\displaystyle x_{i}\leq y_{i}} for all i (Hiraguti 1955, Milner & Pouzet 1990).
Realizers A family R = ( < 1 , … , < t ) {\displaystyle {\mathcal {R}}=(<_{1},\dots ,<_{t})} of total orders on X {\displaystyle X} is called a realizer of a poset P = ( X , < P ) {\displaystyle P=(X,<_{P})} if
< P = ⋂ R {\displaystyle <_{P}=\bigcap {\mathcal {R}}} , which is to say that for any x {\displaystyle x} and y {\displaystyle y} in X {\displaystyle X} , x < P y {\displaystyle x<_{P}y} precisely when x < 1 y , x < 2 y {\displaystyle x<_{1}y,x<_{2}y} ,..., x < t y {\displaystyle x<_{t}y} . Thus, an equivalent definition of the dimension of a poset P {\displaystyle P} is "the least cardinality of a realizer of P {\displaystyle P} ". It can be shown that any nonempty family R {\displaystyle {\mathcal {R}}} of linear extensions is a realizer of a finite partially ordered set P {\displaystyle P} if and only if, for every critical pair ( x , y ) {\displaystyle (x,y)} of , P {\displaystyle P} x < i y {\displaystyle x<_{i}y} for some order < i {\displaystyle <_{i}} in R {\displaystyle {\mathcal {R}}} .
… excerpt ends here. Continue reading the full article.
