Namespaces
Variants
Actions

Difference between revisions of "Sperner theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 34 formulas out of 34 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s1305001.png" />. A family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s1305002.png" /> of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s1305003.png" /> that are pairwise unrelated with respect to inclusion is called a Sperner family (or Sperner system) on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s1305004.png" />. Examples are the families
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
<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/s130500/s1305005.png" /></td> </tr></table>
+
Out of 34 formulas, 34 were replaced by TEX code.-->
 +
 
 +
{{TEX|semi-auto}}{{TEX|done}}
 +
Let $[ n ] : = \{ 1 , \dots , n \}$. A family $\mathcal{F}$ of subsets of $[ n ]$ that are pairwise unrelated with respect to inclusion is called a Sperner family (or Sperner system) on $[ n ]$. Examples are the families
 +
 
 +
\begin{equation*} \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right) : = \{ X \subseteq [ n ] : | X | = k \} , k = 0 , \ldots , n. \end{equation*}
  
 
Since the binomial coefficients satisfy the inequalities
 
Since the binomial coefficients satisfy the inequalities
  
<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/s130500/s1305006.png" /></td> </tr></table>
+
\begin{equation*} \left( \begin{array} { l } { n } \\ { 0 } \end{array} \right) &lt; \ldots &lt; \left( \begin{array} { c } { n } \\ { \lfloor n / 2 \rfloor } \end{array} \right) = \left( \begin{array} { c } { n } \\ { \lceil n / 2 \rceil } \end{array} \right) &gt; \ldots &gt; \left( \begin{array} { l } { n } \\ { n } \end{array} \right), \end{equation*}
  
in these examples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s1305007.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s1305008.png" /> is even, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s1305009.png" /> as well as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050010.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050011.png" /> is odd, have maximum size. Sperner's theorem from 1928 states that these best examples have even maximum size among all Sperner families on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050012.png" /> and that they are the only optimal families.
+
in these examples $\left( \begin{array} { l } { [ n ] } \\ { n / 2 } \end{array} \right)$, if $n$ is even, and $\left( \begin{array} { c } { [ n ] } \\ { ( n - 1 ) / 2 } \end{array} \right)$ as well as $\left( \begin{array} { c } { [ n ] } \\ { ( n + 1 ) / 2 } \end{array} \right)$, if $n$ is odd, have maximum size. Sperner's theorem from 1928 states that these best examples have even maximum size among all Sperner families on $[ n ]$ and that they are the only optimal families.
  
Given a Sperner family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050013.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050015.png" />. In his original proof, E. Sperner used a shifting technique: Consider the smallest <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050016.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050017.png" /> and replace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050018.png" /> by its upper shadow
+
Given a Sperner family $\mathcal{F}$, let $\mathcal{F} _ { k } : = \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right) \cap \mathcal{F}$ and $f _ { k } : = | \cal{F} _ { k } |$. In his original proof, E. Sperner used a shifting technique: Consider the smallest $l$ with $\mathcal{F} _ { l } \neq \emptyset$ and replace $\mathcal{A} : = \mathcal{F} _ { l }$ by its upper shadow
  
<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/s130500/s13050019.png" /></td> </tr></table>
+
\begin{equation*} \nabla ( \mathcal{A} ) : = \left\{ Y \in \left( \begin{array} { l } { [ n ] } \\ { l + 1 } \end{array} \right) : Y \supset X \text { for some } X\in \mathcal{A} \right\}. \end{equation*}
  
Double-counting easily yields <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050020.png" /> and, equivalently,
+
Double-counting easily yields $| {\cal A} | ( n - l ) \leq | \nabla ( {\cal A} ) | ( l + 1 )$ and, 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/s130500/s13050021.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
\begin{equation} \tag{a1} \frac { | \nabla ( {\cal A} ) | } { \left( \begin{array} { c } { n } \\ { l + 1 } \end{array} \right) } \geq \frac { | {\cal A} | } { \left( \begin{array} { l } { n } \\ { l } \end{array} \right) }. \end{equation}
  
 
Thus, each Sperner family can be shifted from below to the  "middle"  and, analogously, from above to the  "middle"  and thereby increasing its size.
 
Thus, each Sperner family can be shifted from below to the  "middle"  and, analogously, from above to the  "middle"  and thereby increasing its size.
  
The inequality (a1) holds for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050022.png" /> and all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050023.png" />, and this property is called the normalized matching property of the lattice of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050024.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050026.png" /> are fixed, the best possible estimate of the upper shadow, and, dually, of the lower shadow (replace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050027.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050028.png" /> and superset by subset), is given by the [[Kruskal–Katona theorem|Kruskal–Katona theorem]].
+
The inequality (a1) holds for all $\mathcal{A} \subseteq \left( \begin{array} { c } { [ n ] } \\ { l } \end{array} \right)$ and all $l$, and this property is called the normalized matching property of the lattice of subsets of $[ n ]$. If $| \cal A |$ and $l$ are fixed, the best possible estimate of the upper shadow, and, dually, of the lower shadow (replace $l + 1$ by $l - 1$ and superset by subset), is given by the [[Kruskal–Katona theorem|Kruskal–Katona theorem]].
  
 
Sperner's theorem follows also easily from the inequality
 
Sperner's theorem follows also easily from the inequality
  
<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/s130500/s13050029.png" /></td> </tr></table>
+
\begin{equation*} \sum _ { k = 0 } ^ { n } \frac { f _ { k } } { \left( \begin{array} { l } { n } \\ { k } \end{array} \right) } \leq 1, \end{equation*}
  
which can be obtained by counting in two different ways the number of pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050030.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050032.png" /> is a permutation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130500/s13050034.png" />. This inequality was proved independently by D. Lubell, S. Yamamoto and L. Meshalkin, and is hence called the LYM inequality; a more general form of it was given by B. Bollobás.
+
which can be obtained by counting in two different ways the number of pairs $( X , \pi )$ where $X \in \mathcal{F}$, $\pi$ is a permutation of $[ n ]$ and $X = \{ \pi ( 1 ) , \ldots , \pi ( | X | ) \}$. This inequality was proved independently by D. Lubell, S. Yamamoto and L. Meshalkin, and is hence called the LYM inequality; a more general form of it was given by B. Bollobás.
  
 
An essential part of Sperner theory consists of the study of other partially ordered sets having analogous properties, e.g. LYM posets and Peck posets (cf. [[Sperner property|Sperner property]]).
 
An essential part of Sperner theory consists of the study of other partially ordered sets having analogous properties, e.g. LYM posets and Peck posets (cf. [[Sperner property|Sperner property]]).
Line 32: Line 40:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  K. Engel,  "Sperner theory" , Cambridge Univ. Press  (1997)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E. Sperner,  "Ein Satz über Untermengen einer endlichen Menge"  ''Math. Z.'' , '''27'''  (1928)  pp. 544–548</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  K. Engel,  "Sperner theory" , Cambridge Univ. Press  (1997)</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  E. Sperner,  "Ein Satz über Untermengen einer endlichen Menge"  ''Math. Z.'' , '''27'''  (1928)  pp. 544–548</td></tr></table>

Revision as of 17:00, 1 July 2020

Let $[ n ] : = \{ 1 , \dots , n \}$. A family $\mathcal{F}$ of subsets of $[ n ]$ that are pairwise unrelated with respect to inclusion is called a Sperner family (or Sperner system) on $[ n ]$. Examples are the families

\begin{equation*} \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right) : = \{ X \subseteq [ n ] : | X | = k \} , k = 0 , \ldots , n. \end{equation*}

Since the binomial coefficients satisfy the inequalities

\begin{equation*} \left( \begin{array} { l } { n } \\ { 0 } \end{array} \right) < \ldots < \left( \begin{array} { c } { n } \\ { \lfloor n / 2 \rfloor } \end{array} \right) = \left( \begin{array} { c } { n } \\ { \lceil n / 2 \rceil } \end{array} \right) > \ldots > \left( \begin{array} { l } { n } \\ { n } \end{array} \right), \end{equation*}

in these examples $\left( \begin{array} { l } { [ n ] } \\ { n / 2 } \end{array} \right)$, if $n$ is even, and $\left( \begin{array} { c } { [ n ] } \\ { ( n - 1 ) / 2 } \end{array} \right)$ as well as $\left( \begin{array} { c } { [ n ] } \\ { ( n + 1 ) / 2 } \end{array} \right)$, if $n$ is odd, have maximum size. Sperner's theorem from 1928 states that these best examples have even maximum size among all Sperner families on $[ n ]$ and that they are the only optimal families.

Given a Sperner family $\mathcal{F}$, let $\mathcal{F} _ { k } : = \left( \begin{array} { c } { [ n ] } \\ { k } \end{array} \right) \cap \mathcal{F}$ and $f _ { k } : = | \cal{F} _ { k } |$. In his original proof, E. Sperner used a shifting technique: Consider the smallest $l$ with $\mathcal{F} _ { l } \neq \emptyset$ and replace $\mathcal{A} : = \mathcal{F} _ { l }$ by its upper shadow

\begin{equation*} \nabla ( \mathcal{A} ) : = \left\{ Y \in \left( \begin{array} { l } { [ n ] } \\ { l + 1 } \end{array} \right) : Y \supset X \text { for some } X\in \mathcal{A} \right\}. \end{equation*}

Double-counting easily yields $| {\cal A} | ( n - l ) \leq | \nabla ( {\cal A} ) | ( l + 1 )$ and, equivalently,

\begin{equation} \tag{a1} \frac { | \nabla ( {\cal A} ) | } { \left( \begin{array} { c } { n } \\ { l + 1 } \end{array} \right) } \geq \frac { | {\cal A} | } { \left( \begin{array} { l } { n } \\ { l } \end{array} \right) }. \end{equation}

Thus, each Sperner family can be shifted from below to the "middle" and, analogously, from above to the "middle" and thereby increasing its size.

The inequality (a1) holds for all $\mathcal{A} \subseteq \left( \begin{array} { c } { [ n ] } \\ { l } \end{array} \right)$ and all $l$, and this property is called the normalized matching property of the lattice of subsets of $[ n ]$. If $| \cal A |$ and $l$ are fixed, the best possible estimate of the upper shadow, and, dually, of the lower shadow (replace $l + 1$ by $l - 1$ and superset by subset), is given by the Kruskal–Katona theorem.

Sperner's theorem follows also easily from the inequality

\begin{equation*} \sum _ { k = 0 } ^ { n } \frac { f _ { k } } { \left( \begin{array} { l } { n } \\ { k } \end{array} \right) } \leq 1, \end{equation*}

which can be obtained by counting in two different ways the number of pairs $( X , \pi )$ where $X \in \mathcal{F}$, $\pi$ is a permutation of $[ n ]$ and $X = \{ \pi ( 1 ) , \ldots , \pi ( | X | ) \}$. This inequality was proved independently by D. Lubell, S. Yamamoto and L. Meshalkin, and is hence called the LYM inequality; a more general form of it was given by B. Bollobás.

An essential part of Sperner theory consists of the study of other partially ordered sets having analogous properties, e.g. LYM posets and Peck posets (cf. Sperner property).

Details can be found in [a1].

References

[a1] K. Engel, "Sperner theory" , Cambridge Univ. Press (1997)
[a2] E. Sperner, "Ein Satz über Untermengen einer endlichen Menge" Math. Z. , 27 (1928) pp. 544–548
How to Cite This Entry:
Sperner theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sperner_theorem&oldid=50377
This article was adapted from an original article by K. Engel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article