Tekst źródłowy strony Twierdzenie Spernera

'''Twierdzenie Spernera<ref name=":0">{{Cytuj |autor = Witold Lipski; Wiktor Marek |tytuł = Analiza kombinatoryczna |data = 1986 |isbn = 9788301049720 |wolumin = 59 |wydawca = Państwowe Wydawnictwo Naukowe |s = 188-189 |seria = Biblioteka Matematyczna |język = pl}}</ref><ref name=":1">{{Cytuj |autor = Beata Bogdańska; Adam Neugebauer |tytuł = Kombinatoryka |data = 2018 |isbn = 9788372677129 |wydawca = Wydawnictwo Szkolne OMEGA |s = 72-73 |seria = Matematyka Olimpijska |język = pl}}</ref>''' – twierdzenie [[Kombinatoryka|kombinatoryczne]] w ekstremalnej teorii zbiorów, określające maksymalną [[Moc zbioru|liczność]] [[Rodzina zbiorów|rodziny zbiorów]], w której żaden zbiór nie jest podzbiorem innego<ref name=":0" /><ref name=":1" />. Twierdzenie to zostało sformułowane przez niemieckiego matematyka [[Emanuel Sperner|Emanuela Spernera]] w 1928 roku<ref>{{Cytuj |autor = Emanuel Sperner |tytuł = Ein Satz über Untermengen einer endlichen Menge |czasopismo = Mathematische Zeitschrift |data = 1928 |data dostępu = 2024-02-28 |issn = 0025-5874 |wolumin = 27 |s = 544–548 |url = https://eudml.org/doc/167993 |język = de |dostęp = o}}</ref>.

== Twierdzenie ==
Rodzinę zbiorów skończonych, w której żaden zbiór nie jest zawarty w innym nazywa się '''rodziną Spernera'''. Rodzina Spernera stanowi [[antyłańcuch]] w [[Częściowy porządek|uporządkowanym]] przez zawieranie <math>\subseteq</math> [[Zbiór potęgowy|zbiorze potęgowym]] <math>\mathcal{P}(A)</math> pewnego skończonego zbioru <math>A.</math> Przykładem rodziny Spernera jest rodzina <math>\mathcal{P}_k(A) </math>wszystkich <math>k</math>-elementowych podzbiorów zbioru <math>A</math> dla pewnego <math>k \le n = |A|,</math> której liczność wynosi <math>\textstyle \binom{n}{k}</math><ref name=":0" />. 

Zgodnie z twierdzeniem Spernera jeśli <math>\mathcal{F}</math> jest rodziną Spernera podzbiorów zbioru <math>n</math>-elementowego <math>A,</math> to<ref name=":0" /><ref name=":1" />{{Wzór|<math>|\mathcal{F}| \le \binom{n}{\lfloor n / 2\rfloor}</math>.}}Równoważnie rodzina <math>\mathcal{P}_{\lfloor n/2\rfloor }(A) </math> jest antyłańcuchem w <math>(\mathcal{P}(A), \subseteq)</math> o maksymalnej liczbie elementów<ref name=":1" />.

== Dowód<ref name=":0" /> ==
Niech <math>\mathcal{F} = \{A_1, A_2, \dots, A_m\}</math> będzie rodziną Spernera podzbiorów zbioru <math>n</math>-elementowego <math>A</math> i niech <math>a_i = |A_i|.</math> Wówczas [[nierówność Lubella-Yamamoto-Meshalkina]] daje
{{Wzór|<math>\sum_{i=1}^m\frac{1}{\binom{n}{a_i} } \le 1</math>.}}

Ponieważ [[Symbol Newtona|współczynniki dwumianowe]] spełniają nierówność
{{Wzór|<math>\binom{n}{k} \le \binom{n}{\lfloor n/2\rfloor}</math>,}}
zachodzi
{{Wzór|<math>1 \ge \sum_{i=1}^m\frac{1}{\binom{n}{a_i}} \ge \sum_{i=1}^m\frac{1}{\binom{n}{\lfloor n/2\rfloor}} = \frac{m}{\binom{n}{\lfloor n/2\rfloor}}</math>,}}
co jest równoważne tezie lematu.

== Uogólnienia ==

=== Wszystkie antyłańcuchy o maksymalnej mocy ===
W 1979 roku Lovász wskazał wszystkie rodziny Spernera podzbiorów zbioru <math>n</math>-elementowego <math>A</math> o maksymalnej liczności. Dla parzystych <math>n</math> taka rodzina jest unikalna i jest nią <math>\mathcal{P}_{n/2}(A). </math> Z kolei dla <math>n</math> nieparzystych są dwie takie rodziny – <math>\mathcal{P}_{\lfloor n/2\rfloor }(A) </math> oraz <math>\mathcal{P}_{\lceil n/2\rceil }(A) </math><ref name=":2">{{Cytuj |autor = Ian Anderson |tytuł = Combinatorics of finite sets |data = 1989 |isbn = 9780198533672 |wydawca = Oxford University Press |s = 3-5 |język = en}}</ref>.

=== Uogólnienie Bollobása (1965) ===
Niech podzbiory <math>A_1, A_2, \dots, A_m </math> oraz <math>B_1, B_2, \dots, B_m </math> zbioru <math>n </math>-elementowego <math>A</math> spełniają warunek <math>A_i \cap B_j = \varnothing </math> wtedy i tylko wtedy, gdy <math>i = j. </math> Wówczas liczby <math>a_i = |A_i| </math> oraz <math>b_i = |B_i| </math> spełniają nierówność
{{Wzór|<math>\sum_{i=1}^m\frac{1}{\binom{a_i+b_i}{a_i} } \le 1</math>.}}
Twierdzenie Spernera otrzymamy, przyjmując <math>B_i = A \setminus A_i </math><ref name=":2" />.

=== Uogólnienie Erdősa (1945) ===
Niech <math>\mathcal{F}</math> będzie rodziną podzbiorów zbioru <math>n </math>-elementowego <math>A.</math> Jeśli nie istnieją różne zbiory <math>A_0, A_1, \dots, A_r \in \mathcal{F}, </math> dla których <math>A_0 \subseteq A_1 \subseteq \dots \subseteq A_r,  </math> to moc rodziny <math>\mathcal{F}</math> jest nie większa od sumy <math>r </math> największych współczynników dwumianowych <math>\textstyle\binom{n}{k} </math><ref>{{Cytuj |autor = Paul Erdős |tytuł = On a lemma of Littlewood and Offord |czasopismo = Bulletin of the American Mathematical Society |data = 1945 |data dostępu = 2024-02-28 |issn = 0002-9904 |wolumin = 51 |numer = 12 |s = 898–902 |doi = 10.1090/S0002-9904-1945-08454-7 |url = https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society-new-series/volume-51/issue-12/On-a-lemma-of-Littlewood-and-Offord/bams/1183507531.full |język = en |dostęp = o}}</ref>. Twierdzenie Spernera stanowi tu przypadek <math>r = 1. </math>

== Zobacz też ==

* [[nierówność Lubella-Yamamoto-Meshalkina]]
* [[twierdzenie Dilwortha]]
* [[twierdzenie Erdősa-Ko-Rado]]

== Przypisy ==
{{Przypisy}}
[[Kategoria:Twierdzenia kombinatoryki]]
[[Kategoria:Rodziny zbiorów]]