Satz von Sperner

Der Satz von Sperner ist ein mathematischer Satz, welcher der diskreten Mathematik zugerechnet wird. Emanuel Sperner hat ihn, ausgehend von einer Anregung seines Doktorvaters Otto Schreier, im Jahre 1927 gefunden und 1928 in der Mathematischen Zeitschrift veröffentlicht. Der Satz behandelt den engen Zusammenhang zwischen den Antiketten der Potenzmenge einer endlichen Menge und den sogenannten Binomialkoeffizienten. Er wurde zum Ausgangspunkt eines Zweiges der diskreten Mathematik, der sogenannten Spernertheorie (englisch Sperner theory). Zum Satz von Sperner gibt es verschiedene Beweise und eine große Anzahl von verwandten Resultaten.

Der Satz in drei Versionen

Für die Darstellung des Satzes gibt es mehrere gleichwertige Möglichkeiten.

Gegeben sei eine endliche Grundmenge ${\displaystyle X}$ mit ${\displaystyle n}$ Elementen, wobei eine natürliche Zahl ${\displaystyle n}$ zugrunde gelegt ist. Dann gilt

Erste Version

Die Mächtigkeit einer jeden Antikette der Potenzmenge ${\displaystyle {\mathcal {P}}(X)}$ ist stets kleiner oder gleich dem größten Binomialkoeffizienten der Ordnung ${\displaystyle n}$.

Der Begriff der Antikette bezieht sich hierbei auf die zwischen den Teilmengen der Grundmenge ${\displaystyle X}$ bestehende Inklusionsrelation.

Zweite Version

Man kann in einer ${\displaystyle n}$ - elementigen Menge ${\displaystyle X}$ niemals mehr als ${\displaystyle {\tbinom {n}{\lfloor {\frac {n}{2}}\rfloor }}}$ Teilmengen finden, welche der Forderung genügen, dass keine zwei dieser Teilmengen einander echt umfassen.

Dritte Version

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

In Worten: Für die Potenzmenge ${\displaystyle {\mathcal {P}}(X)}$ einer ${\displaystyle n\,}$ - elementigen Menge ${\displaystyle X}$ ist die Spernerzahl oder Breite ${\displaystyle w={\binom {n}{\lfloor {\frac {n}{2}}\rfloor }}}$.

In diese formale Darstellung geht ein, dass die ${\displaystyle \lfloor {\tfrac {n}{2}}\rfloor }$-elementigen Teilmengen von ${\displaystyle X}$ stets eine Antikette von ${\displaystyle {\mathcal {P}}(X)}$ bilden.

Der Extremalfall

Emanuel Sperner ist in seinem 1928er Artikel auch der Frage nachgegangen, welche Teilmengensysteme von ${\displaystyle X}$ den Maximalwert ${\displaystyle {\tbinom {n}{\lfloor {\frac {n}{2}}\rfloor }}}$ annehmen, und hat folgende umfassende Antwort gegeben:

Ist ${\displaystyle n}$ eine gerade Zahl, so gibt es stets genau eine Möglichkeit, nämlich das Mengensystem der ${\displaystyle n/2}$-elementigen Teilmengen von ${\displaystyle X}$.

Ist ${\displaystyle n}$ eine ungerade Zahl, so gibt es stets genau zwei Möglichkeiten, nämlich einerseits das Mengensystem der ${\displaystyle (n-1)/2}$-elementigen Teilmengen von ${\displaystyle X}$ und andererseits das Mengensystem der ${\displaystyle (n+1)/2}$-elementigen Teilmengen von ${\displaystyle X}$.

Verwandte Resultate

• Satz von Dilworth
• Lubell-Yamamoto-Meshalkin-Ungleichung
• Satz von Erdős-Ko-Rado

Literatur

Originalarbeiten

• Emanuel Sperner: Ein Satz über Untermengen einer endlichen Menge. In: Math. Z., 27, 1928, S. 544–548. MR1544925
• Hans-Josef Scholz: Über die Kombinatorik der endlichen Potenzmengen im Zusammenhang mit dem Satz von Sperner. Dissertation, Universität Düsseldorf (1987).
• Hans-Joachim Burscheid: Über die Breite des endlichen kardinalen Produktes von endlichen Ketten. In: Math. Nachr., 52, 1972, S. 283–295, MR0307982

Monographien

• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. 2. Auflage. de Gruyter, Berlin (u. a.) 2004, ISBN 3-11-016727-1. 
• Martin Aigner: Combinatorial Theory (= Grundlehren der Mathematischen Wissenschaften. Band 234). Springer Verlag, Berlin (u. a.) 1979, ISBN 3-540-90376-3 (MR0542445). 
• Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie (= Hochschultext). Springer Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1 (MR0460127). 
• Martin Aigner: Diskrete Mathematik (= Dokumente zur Geschichte der Mathematik. Band 6). 6. Auflage. Vieweg Verlag, Wiesbaden 2006, ISBN 978-3-8348-0084-8. 
• Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York 2005, ISBN 0-387-24219-8 (MR2127991). 
• Dieter Jungnickel: Transversaltheorie. Akad. Verl.-Ges. Geest & Portig, Leipzig 1982. 
• Stasys Jukna: Extremal Combinatorics. Springer-Verlag, Heidelberg (u. a.) 2011, ISBN 978-3-642-17363-9. 
• 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. Band 65). Cambridge University Press, Cambridge u. a. 1997, ISBN 0-521-45206-6 (MR1429390). 
• Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan: Combinatorics: The Rota Way (= Cambridge Mathematical Library). Cambridge University Press, Cambridge (u. a) 2009, ISBN 978-0-521-73794-4 (MR2483561). 

Weblinks

• Gy. Károlyi: Lectures on extremal set systems and two-colorings of hypergraphs. (PDF; 243 kB)
• Peter Hauck: Kombinatorische Methoden in der Informatik. (PDF; 1,4 MB) Skript einer Vorlesung, Uni Tübingen, SS 2008