imported>Schojoha: /* Literatur */ Ergänzung Links.

2025-06-28T17:18:24Z

Literatur: Ergänzung Links.

Neue Seite

Der '''Satz von Sperner''' ist ein mathematischer [[Satz (Mathematik)|Satz]], welcher der [[Diskrete Mathematik|diskreten Mathematik]] zugerechnet wird. [[Emanuel Sperner]] hat ihn, ausgehend von einer Anregung seines [[Doktorvater]]s [[Otto Schreier]], im Jahre 1927 gefunden und 1928 in der [[Mathematische Zeitschrift|Mathematischen Zeitschrift]] veröffentlicht. Der Satz behandelt den engen Zusammenhang zwischen den [[Antikette]]n der [[Potenzmenge]] einer [[Endliche Menge|endlichen Menge]] und den sogenannten [[Binomialkoeffizient]]en. 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 Menge|endliche]] [[Grundmenge]] <math>X</math> mit <math>n</math> [[Element (Mathematik)|Elementen]], wobei eine [[natürliche Zahl]] <math>n</math> zugrunde gelegt ist. Dann gilt

=== Erste Version ===

: Die [[Mächtigkeit (Mathematik)|Mächtigkeit]] einer jeden [[Antikette]] der [[Potenzmenge]] <math>\mathcal P(X)</math> ist stets [[Ordnungsrelation|kleiner oder gleich]] dem größten [[Binomialkoeffizient]]en der Ordnung <math>n</math>.

Der Begriff der Antikette bezieht sich hierbei auf die zwischen den [[Teilmenge]]n der [[Grundmenge]] <math>X</math> bestehende [[Mengenlehre|Inklusionsrelation]].

=== Zweite Version ===

: Man kann in einer <math>n</math> - [[Element (Mathematik)|elementigen]] [[Menge (Mathematik)|Menge]] <math>X </math> niemals mehr als <math> \tbinom{n}{\lfloor \frac{n}{2} \rfloor }</math> Teilmengen finden, welche der Forderung genügen, dass keine zwei dieser [[Teilmenge]]n einander [[Teilmenge|echt umfassen]].

=== Dritte Version ===

:<math> \max \{|\mathcal A| : \mathcal A \subseteq \mathcal P(X)\ \mathrm \text{Antikette} \} = \binom{n}{\lfloor \frac n 2 \rfloor }</math>
: In Worten: Für die [[Potenzmenge]] <math>\mathcal P(X)</math> einer <math>n \,</math> - elementigen Menge <math>X</math> ist die [[Spernerzahl]] oder [[Spernerzahl|Breite]] <math>w = \binom{n}{\lfloor \frac n 2 \rfloor }</math>.

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

== Der Extremalfall ==
Emanuel Sperner ist in seinem 1928er Artikel auch der Frage nachgegangen, welche [[Mengensystem|Teilmengensysteme]] von <math>X</math> den Maximalwert <math>\tbinom{n}{\lfloor \frac n 2 \rfloor }</math> annehmen, und hat folgende umfassende Antwort gegeben:
: Ist <math>n</math> eine [[Gerade Zahl#Gerade und ungerade Zahlen|gerade Zahl]], so gibt es stets genau eine Möglichkeit, nämlich das [[Mengensystem]] der <math>n/2</math>-elementigen Teilmengen von <math>X</math>.
: Ist <math>n</math> eine [[Gerade Zahl#Gerade und ungerade Zahlen|ungerade Zahl]], so gibt es stets genau zwei Möglichkeiten, nämlich einerseits das [[Mengensystem]] der <math>(n-1)/2</math>-elementigen Teilmengen von <math>X</math> und andererseits das Mengensystem der <math>(n+1)/2</math>-elementigen Teilmengen von <math>X</math>.

== 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, [http://www.ams.org/mathscinet-getitem?mr=0307982 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. [http://www.ams.org/mathscinet-getitem?mr=1544925 MR1544925]

=== Monographien ===
* {{Literatur
|Autor=[[Martin Aigner]]
|Titel=Kombinatorik II: Matroide und Transversaltheorie
|Reihe=Hochschultext
|Auflage=
|Verlag=Springer Verlag
|Ort=Berlin (u. a.)
|Datum=1976
|ISBN=3-540-07949-1
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Aigner%2C%20Martin&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=80&mx-pid=460127 MR0460127]}}
* {{Literatur
|Autor=[[Martin Aigner]]
|Titel=Combinatorial Theory
|Reihe=Grundlehren der Mathematischen Wissenschaften
|BandReihe=234
|Verlag=[[Springer Science+Business Media|Springer Verlag]]
|Ort=Berlin (u. a.)
|Datum=1979
|ISBN=3-540-90376-3
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Aigner%2C%20Martin&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=76&mx-pid=542445 MR0542445]}}
* {{Literatur
|Autor=Martin Aigner
|Titel=Diskrete Mathematik
|Reihe=Dokumente zur Geschichte der Mathematik
|BandReihe=6
|Auflage=6.
|Verlag=Vieweg Verlag
|Ort=Wiesbaden
|Datum=2006
|ISBN=978-3-8348-0084-8}}
* {{Literatur
|Autor=Ian Anderson
|Titel=Combinatorics of Finite Sets
|Verlag=Clarendon Press
|Ort=Oxford
|Datum=1987
|ISBN=0-19-853367-5
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Anderson%2C%20Ian%20&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=63&mx-pid=892525 MR0892525]}}
* {{Literatur
|Autor=[[Konrad Engel (Mathematiker)|Konrad Engel]]
|Titel=Sperner Theory
|Reihe=Encyclopedia of Mathematics and its Applications
|BandReihe=65
|Verlag=Cambridge University Press
|Ort=Cambridge u. a.
|Datum=1997
|ISBN=0-521-45206-6
|Online=[https://mathscinet.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=TI&pg7=ALLF&pg8=ET&review_format=html&s4=Engel&s5=Sperner&s6=Theory&s7=&s8=All&sort=Newest&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=1&mx-pid=1429390 MR1429390]}}
* {{Literatur
|Autor=[[Egbert Harzheim]]
|Titel=Ordered Sets
|Reihe=Advances in Mathematics
|BandReihe=7
|Verlag=Springer Verlag
|Ort=New York
|Datum=2005
|ISBN=0-387-24219-8
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Harzheim%2C%20Egbert&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=3&mx-pid=2127991 MR2127991]}}
* {{Literatur
|Autor=Joseph P. S. Kung, [[Gian-Carlo Rota]], Catherine H. Yan
|Titel=Combinatorics: The Rota Way
|Reihe=Cambridge Mathematical Library
|Verlag=Cambridge University Press
|Ort=Cambridge (u. a.)
|Datum=2009
|ISBN=978-0-521-73794-4
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Rota%2C%20Gian-Carlo&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=2&mx-pid=2483561 MR2483561]}}
* {{Literatur
|Autor=[[Konrad Jacobs]], [[Dieter Jungnickel]]
|Titel=Einführung in die Kombinatorik
|Auflage=2.
|Verlag=de Gruyter
|Ort=Berlin (u. a.)
|Datum=2004
|ISBN=3-11-016727-1}}
* {{Literatur
|Autor=Dieter Jungnickel
|Titel=Transversaltheorie
|Verlag=Akad. Verl.-Ges. Geest & Portig
|Ort=Leipzig
|Datum=1982}}
* {{Literatur
|Autor=[[Stasys Jukna]]
|Titel=Extremal Combinatorics
|Verlag=Springer-Verlag
|Ort=Heidelberg (u. a.)
|Datum=2011
|ISBN=978-3-642-17363-9}}

== Weblinks ==
* Gy. Károlyi: [http://www.cs.elte.hu/~karolyi/tempus.pdf ''Lectures on extremal set systems and two-colorings of hypergraphs''.] (PDF; 243 kB)
* Peter Hauck: [http://www-dm.informatik.uni-tuebingen.de/skripte/Kombinatorik/KombinatorikSS2008.pdf ''Kombinatorische Methoden in der Informatik''.] (PDF; 1,4 MB) Skript einer Vorlesung, Uni Tübingen, SS 2008
* {{MathWorld|title=Sperner's Theorem|urlname=SpernersTheorem}}

[[Kategorie:Diskrete Mathematik]]
[[Kategorie:Satz (Mathematik)|Sperner, Satz von]]

Satz von Sperner - Versionsgeschichte

imported>Schojoha: /* Literatur */ Ergänzung Links.