Satz von Sperner

Der Satz v​on Sperner i​st ein mathematischer Satz, welcher d​er diskreten Mathematik zugerechnet wird. Emanuel Sperner h​at ihn, ausgehend v​on einer Anregung seines Doktorvaters Otto Schreier, i​m Jahre 1927 gefunden u​nd 1928 i​n der Mathematischen Zeitschrift veröffentlicht. Der Satz behandelt d​en engen Zusammenhang zwischen d​en Antiketten d​er Potenzmenge e​iner endlichen Menge u​nd den sogenannten Binomialkoeffizienten. Er w​urde zum Ausgangspunkt e​ines Zweiges d​er diskreten Mathematik, d​er sogenannten Spernertheorie (englisch Sperner theory). Zum Satz v​on Sperner g​ibt es verschiedene Beweise u​nd eine große Anzahl v​on verwandten Resultaten.

Der Satz in drei Versionen

Für d​ie Darstellung d​es Satzes g​ibt 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

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

Monographien

• Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie (= Hochschultext). Springer Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1 (MR0460127).
• Martin Aigner: Combinatorial Theory (= Grundlehren der Mathematischen Wissenschaften. Band 234). Springer Verlag, Berlin (u. a.) 1979, ISBN 3-540-90376-3 (MR0542445).
• Martin Aigner: Diskrete Mathematik (= Dokumente zur Geschichte der Mathematik. Band 6). 6. Auflage. 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. Band 65). Cambridge University Press, Cambridge u. a. 1997, ISBN 0-521-45206-6 (MR1429390).
• Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York 2005, ISBN 0-387-24219-8 (MR2127991).
• 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).
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. 2. Auflage. de Gruyter, Berlin (u. a.) 2004, ISBN 3-11-016727-1.
• 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.

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