dimension of a poset


Let P be a finite poset and be the family of all realizersMathworldPlanetmath of P. The dimensionPlanetmathPlanetmath of P, written dim(P), is the cardinality of a member E with the smallest cardinality. In other words, the dimension n of P is the least number of linear extensions L1,,Ln of P such that P=L1Ln. (E can be chosen to be {L1,,Ln}).

If P is a chain, then dim(P)=1. The converseMathworldPlanetmath is clearly true too. An example of a poset with dimension 2 is an antichainMathworldPlanetmath with at least 2 elements. For if P={a1,,am} is an antichain, then one way to linearly extend P is to simply put aiaj iff ij. Called this extensionPlanetmathPlanetmath L1. Another way to order P is to reverse L1, by aiaj iff ji. Call this L2. Note that L1 and L2 are duals of each other. Let L=L1L2. As both L1 and L2 are linear extensions of P, PL. On the other hand, if (ai,aj)L, then aiaj in both L1 and L2, so that ij and ji, or i=j and whence ai=aj, which implies (ai,aj)=(ai,ai)P. LP and thus dim(P)=2.

Remark. Let P be a finite poset. A theoremMathworldPlanetmath of Dushnik and Miller states that the smallest n such that P can be embedded in n, considered as the n-fold product of posets, or chains of real numbers , is the dimension of P.

References

Title dimension of a poset
Canonical name DimensionOfAPoset
Date of creation 2013-03-22 16:33:29
Last modified on 2013-03-22 16:33:29
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Definition
Classification msc 06A06
Classification msc 06A07
Defines dimension