Satz von Sperner

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).

Inhaltsverzeichnis

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

Literatur

  • Konrad Engel: Sperner Theory. Cambridge University Press, Cambridge, New York 1997, ISBN 0-521-45206-6.
  • 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"

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Emanuel Sperner — (* 9. Dezember 1905 in Waltdorf bei Neisse, Oberschlesien; † 31. Januar 1980 in Laufen, Markgräflerland) war ein deutscher Mathematiker, der für zwei nach ihm benannte Sätze bekannt ist …   Deutsch Wikipedia

  • Lubell-Yamamoto-Meshalkin-Ungleichung — Die Lubell Yamamoto Meshalkin Ungleichung oder auch LYM Ungleichung ist ein Resultat, welches mit dem Satz von Sperner eng verwandt ist und diesen sogar verallgemeinert. Ebenso wie bei dem Satz von Sperner geht es auch bei der LYM Ungleichung um… …   Deutsch Wikipedia

  • Das BUCH der Beweise — (engl. Proofs from THE BOOK) ist ein Buch der Mathematiker Martin Aigner und Günter M. Ziegler, das besonders schöne Beweise enthalten soll. Es wurde 1998 auf Englisch und 2002 auf Deutsch herausgegeben sowie in weiteren Sprachen veröffentlicht.… …   Deutsch Wikipedia

  • Liste mathematischer Sätze — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Satz von Abel Ruffini: eine allgemeine Polynomgleichung vom …   Deutsch Wikipedia

  • Antikette — Der Begriff der Antikette (engl. antichain) ist ein Begriff der Mengenlehre und gehört zum Umfeld des Begriffs der Ordnungsrelation. Die Definition dieses Begriffs ist wie folgt: Eine Teilmenge A einer geordneten Menge (M, R) ist eine Antikette,… …   Deutsch Wikipedia

  • Otto Schreier — (* 3. März 1901 in Wien; † 2. Juni 1929 in Hamburg) war ein österreichischer Mathematiker, der sich mit kombinatorischer Gruppentheorie beschäftigte und u. a. mit dem Satz von Nielsen Schreier bekannt wurde. Schreier studierte ab 1920 an der… …   Deutsch Wikipedia

  • Gerhard Ringel — (* 28. Oktober 1919 in Kollnbrunn, Österreich; † 24. Juni 2008 in Santa Cruz, USA) war ein renommierter Mathematiker und Pionier im Bereich Kombinatorik und Graphentheorie. Gerhard Ringel beim Surfen …   Deutsch Wikipedia

  • Liste de théorèmes — par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom du théorème comprend des noms de mathématiciens ou de physiciens, on se base sur le premier nom propre cité. Si le nom du théorème …   Wikipédia en Français

  • Schreier — Schrei|er 〈m. 3〉 1. jmd., der viel schreit (bes. Kind) 2. 〈fig.〉 aufsässiger, rechthaberischer, zänkischer Mensch, Unruhestifter ● diesem Schreier sollte man endlich den Mund stopfen 〈fig.; umg.〉 [<mhd. schri(g)er „Ausrufer, Herold“] * * *… …   Universal-Lexikon

  • Seiteneinteilung — In der elementaren Geometrie der Zeichenebene zerlegt jede Gerade die Ebene in zwei (offene) Halbebenen, die Seiten der Gerade, diese Beobachtung ist zunächst der Anschauung entnommen. Diese Seiteneinteilung lässt sich mathematisch beschreiben… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”