Satz von Sperner
Der Satz in drei Versionen
Für die Darstellung des Satzes gibt es mehrere gleichwertige Möglichkeiten.
Gegeben sei eine endliche Grundmenge mit Elementen, wobei eine natürliche Zahl zugrunde gelegt ist. Dann gilt
Dritte Version
- In Worten: Für die Potenzmenge einer - elementigen Menge ist die Spernerzahl oder Breite .
In diese formale Darstellung geht ein, dass die -elementigen Teilmengen von stets eine Antikette von bilden.
Der Extremalfall
Emanuel Sperner ist in seinem 1928er Artikel auch der Frage nachgegangen, welche Teilmengensysteme von den Maximalwert annehmen, und hat folgende umfassende Antwort gegeben:
- Ist eine gerade Zahl, so gibt es stets genau eine Möglichkeit, nämlich das Mengensystem der -elementigen Teilmengen von .
- Ist eine ungerade Zahl, so gibt es stets genau zwei Möglichkeiten, nämlich einerseits das Mengensystem der -elementigen Teilmengen von und andererseits das Mengensystem der -elementigen Teilmengen von .
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.