Sperner's theorem

The set of Sperner is a mathematical theorem which of the discrete mathematics is attributed. Emanuel Sperner found it, based on a suggestion from his doctoral supervisor Otto Schreier , in 1927 and published it in the Mathematische Zeitschrift in 1928 . The theorem deals with the close connection between the anti-chains of the power set of a finite set and the so-called binomial coefficients . It became the starting point of a branch of discrete mathematics, the so-called Sperner theory (English Sperner theory ). There are various proofs and a large number of related results for Sperner's theorem.

The set in three versions

There are several equivalent options for representing the sentence.

A finite basic set with elements is given , based on a natural number . Then applies ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle n}$

First version

The thickness of each anti-chain of the power set is always less than or equal to the largest binomial coefficient of the order . ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle n}$

The concept of antichain here refers to the between the subsets of the ground set existing inclusion relation . ${\displaystyle X}$

Second version

One can never find more than subsets in an - elementary set which satisfy the requirement that no two of these subsets really include each other . ${\displaystyle n}$ ${\displaystyle X}$ ${\displaystyle {\tbinom {n}{\lfloor {\frac {n}{2}}\rfloor }}}$

Third version

${\displaystyle \max\{|{\mathcal {A}}|:{\mathcal {A}}\subseteq {\mathcal {P}}(X)\ \mathrm {\text{Antikette}} \}={\binom {n}{\lfloor {\frac {n}{2}}\rfloor }}}$

In words: For the power set of a - elementary set is the Sperner number or width . ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle n\,}$ ${\displaystyle X}$ ${\displaystyle w={\binom {n}{\lfloor {\frac {n}{2}}\rfloor }}}$

This formal representation implies that the -element subsets of always form an anti-chain of . ${\displaystyle \lfloor {\tfrac {n}{2}}\rfloor }$ ${\displaystyle X}$ ${\displaystyle {\mathcal {P}}(X)}$

The extreme case

Emanuel Sperner is in his 1928 article also explored the question of which subset of systems of the maximum value assumed and gave the following global response: ${\displaystyle X}$ ${\displaystyle {\tbinom {n}{\lfloor {\frac {n}{2}}\rfloor }}}$

If it is an even number , then there is always exactly one possibility, namely the set system of -element subsets of . ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle X}$

Is an odd number , so there are always two choices, on the one hand the quantity system of -element subsets of and secondly the amount of system -element subsets of . ${\displaystyle n}$ ${\displaystyle (n-1)/2}$ ${\displaystyle X}$ ${\displaystyle (n+1)/2}$ ${\displaystyle X}$

Related results

• Dilworth theorem
• Lubell-Yamamoto-Meshalkin inequality
• Erdős-Ko-Rado's theorem

literature

Original work

• Hans-Joachim Burscheid: About the breadth of the finite cardinal product of finite chains . In: Math. Nachr. , 52, 1972, pp. 283-295, MR0307982
• Hans-Josef Scholz: About the combinatorics of finite power sets in connection with Sperner's theorem . Dissertation, University of Düsseldorf (1987).
• Emanuel Sperner : A theorem about subsets of a finite set . In: Math. Z. , 27, 1928, pp. 544-548. MR1544925

Monographs

• Martin Aigner : Combinatorics II: Matroids and transversal theory (=  university text ). Springer Verlag, Berlin ( inter alia ) 1976, ISBN 3-540-07949-1 ( MR0460127 ).
• Martin Aigner : Combinatorial Theory (=  Basic Teachings of Mathematical Sciences . Volume 234 ). Springer Verlag , Berlin ( inter alia ) 1979, ISBN 3-540-90376-3 ( MR0542445 ).
• Martin Aigner: Discrete Mathematics (=  documents on the history of mathematics . Volume 6 ). 6th edition. Vieweg Verlag, Wiesbaden 2006, ISBN 978-3-8348-0084-8 .
• Ian Anderson: Combinatorics of Finite Sets . Clarendon Press, Oxford 1987, ISBN 0-19-853367-5 ( MR0892525 ).
• Konrad Engel: Sperner Theory (=  Encyclopedia of Mathematics and its Applications . Volume 65 ). Cambridge University Press, Cambridge u. a. 1997, ISBN 0-521-45206-6 ( MR1429390 ).
• Egbert Harzheim : Ordered Sets (=  Advances in Mathematics . Volume 7 ). Springer Verlag, New York 2005, ISBN 0-387-24219-8 ( MR2127991 ).
• Joseph PS Kung, Gian-Carlo Rota , Catherine H. Yan: Combinatorics: The Rota Way (=  Cambridge Mathematical Library ). Cambridge University Press, Cambridge (et al.) 2009, ISBN 978-0-521-73794-4 ( MR2483561 ).
• Konrad Jacobs , Dieter Jungnickel : Introduction to combinatorics . 2nd Edition. de Gruyter, Berlin (et al.) 2004, ISBN 3-11-016727-1 .
• Dieter Jungnickel : Transversal Theory . Akad. Verl.-Ges. Geest & Portig, Leipzig 1982.
• Stasys Jukna: Extremal Combinatorics . Springer-Verlag, Heidelberg (inter alia) 2011, ISBN 978-3-642-17363-9 .

Web links

• Gy. Károlyi: Lectures on extremal set systems and two-colorings of hypergraphs . (PDF; 243 kB)
• Peter Hauck: Combinatorial Methods in Computer Science . (PDF; 1.4 MB) Lecture notes, University of Tübingen, SS 2008