Satz von Sperner

Der Satz von Sperner ist ein mathematischer Lehrsatz, welcher der diskreten Mathematik zugerechnet wird. Er wurde von Emanuel Sperner im Jahr 1928 veröffentlicht. Der Satz behandelt den engen Zusammenhang zwischen den Antiketten der Potenzmenge einer endlichen Menge und den Binomialkoeffizienten. Er wurde zum Ausgangspunkt eines Zweiges der diskreten Mathematik, der sogenannten Spernertheorie (engl. Sperner theory). Zum Satz von Sperner gibt es mehrere verschiedene Beweise und eine große Anzahl von verwandten Resultaten. Einen guten Eindruck davon verschaffen die Monographien von Anderson, von Engel und von Jukna (siehe Literatur).

Der Satz

Gegeben sei eine endliche Grundmenge X mit n Elementen, wobei n eine natürliche Zahl sei. Dann gilt:

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

Der Begriff der Antikette bezieht sich hierbei auf die zwischen den Teilmengen der Grundmenge X bestehende Inklusionsrelation.

Der Satz lautet in anderer Formulierung also:

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

Der Satz lässt sich – unter Berücksichtigung der Tatsache, dass die $\lfloor \tfrac{n}{2} \rfloor$ -elementigen Teilmengen von X stets eine Antikette von $\mathcal P(X)$ bilden – in Formelschreibweise auch so ausdrücken:

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

Der Extremalfall

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

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

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

Verwandte Resultate

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

Literatur

• Martin Aigner: Combinatorial Theory. Springer, Berlin (u. a.) 1979, ISBN 3-540-90376-3.

• Martin Aigner: Diskrete Mathematik. 6. Auflage. Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8.

• Ian Anderson: Combinatorics of Finite Sets. Clarendon Press, Oxford 1987, ISBN 0-19-853367-5.

• Konrad Engel: Sperner Theory. Cambridge University Press, Cambridge, New York 1997, ISBN 0-521-45206-6.

• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. 2. Auflage. de Gruyter, Berlin, New York 2004, ISBN 3-11-016727-1.

• Dieter Jungnickel: Transversaltheorie. Akad. Verl.-Ges. Geest & Portig, Leipzig 1982.

• Stasys Jukna: Extremal Combinatorics. Springer, Berlin (u. a.) 2001, ISBN 3-540-66313-4.

Weblinks

• [1] Link ins englische WIKIPEDIA zu "Sperner family"