View source for Sperner property

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s1304901.png" /> be a finite [[Partially ordered set|partially ordered set]] (abbreviated: poset) which possesses a rank function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s1304902.png" />, i.e. a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s1304903.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s1304904.png" /> for some minimal element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s1304905.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s1304906.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s1304907.png" /> whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s1304908.png" /> covers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s1304909.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049010.png" /> and there is no element between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049012.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049013.png" /> be its <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049014.png" />th level and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049015.png" /> be the rank of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049016.png" />.

An [[anti-chain]] or Sperner family in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049017.png" /> is a subset of pairwise incomparable elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049018.png" />. Obviously, each level is an anti-chain. The [[width of a partially ordered set]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049019.png" /> (Dilworth number or Sperner number) is the maximum size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049020.png" /> of an anti-chain of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049021.png" />. The poset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049022.png" /> is said to have the Sperner property if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049023.png" />. E. Sperner proved in 1928 the Sperner property for Boolean lattices (cf. also [[Sperner theorem|Sperner theorem]]).

More generally, a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049025.png" />-family, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049026.png" />, is a subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049027.png" /> containing no chain of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049028.png" /> elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049029.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049030.png" /> has the strong Sperner property if for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049031.png" /> the largest size of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049032.png" />-family in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049033.png" /> equals the largest size of a union of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049034.png" /> levels. There exist several classes of posets having the strong Sperner property:

LYM posets, i.e. posets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049035.png" /> satisfying the LYM inequality (cf. also [[Sperner theorem|Sperner theorem]])

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049036.png" /></td> </tr></table>

for every anti-chain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049037.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049038.png" /> or, equivalently,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049039.png" /></td> </tr></table>

for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049041.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049042.png" />. This equivalent property is called the normalized matching property of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049043.png" />.

Symmetric chain orders, i.e. ranked posets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049044.png" /> which can be decomposed into chains of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049045.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049046.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049047.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049048.png" />.

Peck posets, i.e. ranked posets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049049.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049050.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049051.png" /> and there is a linear operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049052.png" /> on the vector space having the basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049053.png" /> with the following properties:

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049054.png" /> with some numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049055.png" />,

the subspace generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049056.png" /> is mapped via <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049057.png" /> to a subspace of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049058.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049059.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049060.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049061.png" /> are posets from one class, then also the direct product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049062.png" /> (ordered componentwise) belongs to that class, where in the case of LYM posets an additional condition must be supposed: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049063.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049064.png" /> (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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049065.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049066.png" />-dimensional vector space over a finite field, ordered by inclusion. The poset of faces of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049067.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130490/s13049068.png" /> is sufficiently large.

Details can be found in [[#References|[a1]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Engel,   "Sperner theory" , Cambridge Univ. Press  (1997)</TD></TR></table>