Sperner property

Let $P$ be a finite partially ordered set (abbreviated: poset) which possesses a rank function $r$, i.e. a function $r : P \rightarrow \mathbf{N}$ such that $r ( p ) = 0$ for some minimal element $p$ of $P$ and $r ( q ) = r ( p ) + 1$ whenever $q$ covers $p$, i.e. $p < q$ and there is no element between $p$ and $q$. Let $N _ { k } : = \{ p \in P : r ( p ) = k \}$ be its $k$th level and let $r ( P ) : = \operatorname { max } \{ r ( p ) : p \in P \}$ be the rank of $P$.

An anti-chain or Sperner family in $P$ is a subset of pairwise incomparable elements of $P$. Obviously, each level is an anti-chain. The width of a partially ordered set $P$ (Dilworth number or Sperner number) is the maximum size $d ( P )$ of an anti-chain of $P$. The poset $P$ is said to have the Sperner property if $d ( P ) = \operatorname { max } _ { k } | N _ { k } |$. E. Sperner proved in 1928 the Sperner property for Boolean lattices (cf. also Sperner theorem).

More generally, a $k$-family, $k = 1 , \ldots , r ( P )$, is a subset of $P$ containing no chain of $k + 1$ elements in $P$, and $P$ has the strong Sperner property if for each $k$ the largest size of a $k$-family in $P$ equals the largest size of a union of $k$ levels. There exist several classes of posets having the strong Sperner property:

LYM posets, i.e. posets $P$ satisfying the LYM inequality

$$\begin{equation*} \sum _ { k = 0 } ^ { r ( P ) } \frac { | \mathcal{F} \cap N _ { k } | } { | N _ { k } | } \leq 1 \end{equation*}$$

for every anti-chain $\mathcal{F}$ in $P$ or, equivalently,

$$\begin{equation*} \frac { | \nabla ( {\cal A} ) | } { | N _ { k + 1} | } \geq \frac { | {\cal A} | } { | N _ { k } | } \end{equation*}$$

for all $A \subseteq N _ { k }$, $k = 0 , \ldots , r ( P ) - 1$, where $\nabla ( \mathcal{A} ) : = \{ q \in N _ { k + 1} : q > p \ \text { for some } p \in \mathcal{A} \}$. This equivalent property is called the normalized matching property of $P$.

Symmetric chain orders, i.e. ranked posets $P$ which can be decomposed into chains of the form $( p _ { 0 } < \cdots < p _ { h } )$ where $r ( p _ { i } ) = r ( p _ { 0 } ) + i$, $i = 0 , \ldots , h$, and $r ( p _ { 0 } ) + r ( p _ { h } ) = r ( P )$.

Peck posets, i.e. ranked posets $P$ such that $| N _ { k } | = | N _ { r(P)-k} |$ for all $k$ and there is a linear operator $\tilde { \nabla }$ on the vector space having the basis $\{ \tilde{p} : p \in P \}$ with the following properties:

• $\widetilde{\nabla}(\tilde p) = \sum_{q:\,q\,\text{covers}\,p} c(p,q)\,\tilde q$ with some numbers $c ( p , q )$,
• the subspace generated by $\{ \tilde { p } : p \in N _ { i } \}$ is mapped via $\widetilde { \nabla } ^ { j - i }$ to a subspace of dimension $\min\{|N_i|,|N_j|\}$ for all $0 \leq i < j \leq r ( P )$.

If $P$ and $Q$ are posets from one class, then also the direct product $P \times Q$ (ordered componentwise) belongs to that class, where in the case of LYM posets an additional condition must be supposed: $| N _ { k } | ^ { 2 } \geq | N _ { k - 1} | | N _ { k + 1}|$ for all $k$ (so-called logarithmic concavity). Moreover, quotient theorems have been proved for LYM posets with weight functions and Peck posets.

Every LYM poset with the symmetry and unimodality property $| N _ { 0 } | = | N _ { r(P) } | \leq | N _ { 1 } | = | N _ { r ( P ) - 1} | \leq \dots$ is a symmetric chain order and every symmetric chain order is a Peck poset.

Standard examples of posets belonging to all these three classes are the lattice of subsets of a finite set, ordered by inclusion (the Boolean lattice), the lattice of divisors of a natural number, ordered by divisibility, the lattice of all subspaces of an $n$-dimensional vector space over a finite field, ordered by inclusion. The poset of faces of an $n$-dimensional cube, ordered by inclusion, belongs only to the class of LYM posets. The lattice of partitions of a finite set, ordered by refinement, even does not have the Sperner property if $n$ is sufficiently large.

Details can be found in [a1].

References

• [a1] K. Engel, Sperner Theory, Encyclopedia of Mathematics and its Applications 65, Cambridge (1997) ISBN 0-521-45206-6 Zbl 0868.05001