„Satz von Sperner“ – Versionsunterschied
[ungesichtete Version] | [gesichtete Version] |
Hinzufügung von Quellen. Kleinere Korrekturen |
Leichte Umformulierung bei der dritten Version. Literatur aktualisiert. |
||
Zeile 22: | Zeile 22: | ||
:''<math> \max \{|\mathcal A| : \mathcal A \subseteq \mathcal P(X)\ \mathrm{Antikette} \} = \binom{n}{\lfloor \frac n 2 \rfloor }</math>'' |
:''<math> \max \{|\mathcal A| : \mathcal A \subseteq \mathcal P(X)\ \mathrm{Antikette} \} = \binom{n}{\lfloor \frac n 2 \rfloor }</math>'' |
||
:In Worten: '' |
:In Worten: ''Für die [[Potenzmenge]] <math>\mathcal P(X)</math> einer <math>n \,</math> - [[element]]igen [[Menge]] <math>X \,</math> ist die [[Antikette|Sperner-Zahl]] oder [[Antikette|Breite]] <math> w = \binom{n}{\lfloor \frac n 2 \rfloor }</math> .'' |
||
In diese [[Formel_(Mathematik)|formale]] Darstellung geht ein, dass die <math>\lfloor \tfrac{n}{2} \rfloor </math> -[[element]]igen Teilmengen von <math>X \,</math> stets eine [[Antikette]] von <math> \mathcal P(X) </math> bilden. |
In diese [[Formel_(Mathematik)|formale]] Darstellung geht ein, dass die <math>\lfloor \tfrac{n}{2} \rfloor </math> -[[element]]igen Teilmengen von <math>X \,</math> stets eine [[Antikette]] von <math> \mathcal P(X) </math> bilden. |
||
Zeile 43: | Zeile 43: | ||
* [[Emanuel Sperner]]: ''Ein Satz über Untermengen einer endlichen Menge''. Math. Z. 27 (1928): 544–548. [http://www.ams.org/mathscinet-getitem?mr=1544925 MR] |
* [[Emanuel Sperner]]: ''Ein Satz über Untermengen einer endlichen Menge''. Math. Z. 27 (1928): 544–548. [http://www.ams.org/mathscinet-getitem?mr=1544925 MR] |
||
=== Monographien === |
=== Monographien === |
||
* {{Literatur |
|||
|Autor=[[Martin Aigner]] |
|||
|Titel=Kombinatorik II: Matroide und Transversaltheorie |
|||
|Auflage= |
|||
|Verlag=[[Springer-Verlag]] |
|||
|Ort=Berlin (u. a.) |
|||
|Jahr=1976 |
|||
|ISBN=3-540-07949-1 |
|||
}} |
|||
* {{Literatur |
* {{Literatur |
||
|Autor=[[Martin Aigner]] |
|Autor=[[Martin Aigner]] |
||
|Titel=Combinatorial Theory |
|Titel=Combinatorial Theory |
||
|Verlag=Springer |
|Verlag=[[Springer-Verlag]] |
||
|Ort=Berlin (u. a.) |
|Ort=Berlin (u. a.) |
||
|Jahr=1979 |
|Jahr=1979 |
||
Zeile 59: | Zeile 68: | ||
|Titel=Diskrete Mathematik |
|Titel=Diskrete Mathematik |
||
|Auflage=6. |
|Auflage=6. |
||
|Verlag=Vieweg |
|Verlag=[[Vieweg]] |
||
|Ort=Wiesbaden |
|Ort=Wiesbaden |
||
|Jahr=2006 |
|Jahr=2006 |
||
Zeile 78: | Zeile 87: | ||
|Autor=Konrad Engel |
|Autor=Konrad Engel |
||
|Titel=Sperner Theory |
|Titel=Sperner Theory |
||
|Verlag=Cambridge University Press |
|Verlag=[[Cambridge University Press]] |
||
|Ort=Cambridge |
|Ort=Cambridge (u. a.) |
||
|Jahr=1997 |
|Jahr=1997 |
||
|ISBN=0-521-45206-6 |
|ISBN=0-521-45206-6 |
||
}} |
|||
* {{Literatur |
|||
|Autor=Egbert Harzheim |
|||
|Titel=Ordered Sets |
|||
|Verlag=[[Springer]] |
|||
|Ort=New York |
|||
|Jahr=2005 |
|||
|ISBN=0-387-24219-8 |
|||
}} |
}} |
||
Zeile 97: | Zeile 115: | ||
|Titel=Einführung in die Kombinatorik |
|Titel=Einführung in die Kombinatorik |
||
|Auflage=2. |
|Auflage=2. |
||
|Verlag=de Gruyter |
|Verlag=[[de Gruyter]] |
||
|Ort=Berlin |
|Ort=Berlin (u. a.) |
||
|Jahr=2004 |
|Jahr=2004 |
||
|ISBN=3-11-016727-1 |
|ISBN=3-11-016727-1 |
||
Zeile 114: | Zeile 132: | ||
|Autor=Stasys Jukna |
|Autor=Stasys Jukna |
||
|Titel=Extremal Combinatorics |
|Titel=Extremal Combinatorics |
||
|Verlag=Springer |
|Verlag=[[Springer-Verlag]] |
||
|Ort= |
|Ort=Heidelberg (u. a.) |
||
|Jahr= |
|Jahr=2011 |
||
|ISBN=3- |
|ISBN=978-3-642-17363-9 |
||
}} |
}} |
||
Zeile 124: | Zeile 142: | ||
* [http://en.wikipedia.org/wiki/Sperner_family] Link ins englische WIKIPEDIA zu "Sperner family" |
* [http://en.wikipedia.org/wiki/Sperner_family] Link ins englische WIKIPEDIA zu "Sperner family" |
||
* [http://www.cs.elte.hu/~karolyi/tempus.pdf] Link zu "Lectures on extremal set systems and two-colorings of hypergraphs" von Gy. Károlyi |
* [http://www.cs.elte.hu/~karolyi/tempus.pdf] Link zu "Lectures on extremal set systems and two-colorings of hypergraphs" von Gy. Károlyi |
||
* |
* [http://www-dm.informatik.uni-tuebingen.de/skripte/Kombinatorik/KombinatorikSS2008.pdf] ''Kombinatorische Methoden in der Informatik'' (Skript einer Vorlesung von Prof. Dr. Peter Hauck, Uni Tübingen, SS 2008) |
||
Version vom 25. November 2011, 19:22 Uhr
Der Satz von Sperner ist ein mathematischer Lehrsatz, welcher der diskreten Mathematik zugerechnet wird. Emanuel Sperner hat ihn, ausgehend von einer Anregung seines Doktorvaters Otto Schreier, im Jahre 1927 gefunden und im Jahre 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. Einen guten Eindruck davon verschaffen die Monographien von Anderson, von Engel und von Jukna (siehe Literatur).
Für die Darstellung des Satzes gibt es mehrere gleichwertige Möglichkeiten.
Der Satz in drei Versionen
Gegeben sei eine endliche Grundmenge mit Elementen, wobei eine natürliche Zahl zugrunde gelegt ist.
Dann gilt:
Erste Version
- Die Mächtigkeit einer jeden Antikette der Potenzmenge ist stets kleiner oder gleich dem größten Binomialkoeffizienten der Ordnung .
Der Begriff der Antikette bezieht sich hierbei auf die zwischen den Teilmengen der Grundmenge bestehende Inklusionsrelation.
Zweite Version
- Man kann in einer - elementigen Menge niemals mehr als Teilmengen finden, welche der Forderung genügen, dass keine zwei dieser Teilmengen einander echt umfassen.
Dritte Version
- In Worten: Für die Potenzmenge einer - elementigen Menge ist die Sperner-Zahl 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 1928-er 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 .
Verwandte Resultate
Literatur
Originalarbeiten
- Hans-Joachim Burscheid: Über die Breite des endlichen kardinalen Produktes von endlichen Ketten. Math. Nachr. 52 (1972): 283–295. MR
- 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. Math. Z. 27 (1928): 544–548. MR
Monographien
- Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie. Springer-Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1.
- Martin Aigner: Combinatorial Theory. Springer-Verlag, 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 (u. a.) 1997, ISBN 0-521-45206-6.
- Egbert Harzheim: Ordered Sets. Springer, New York 2005, ISBN 0-387-24219-8.
- Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan: Combinatorics: The Rota Way. Cambridge University Press, Cambridge (u. a) 2009, ISBN 978-0-521-73794-4.
- 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.