Twierdzenie Spernera

Twierdzenie Spernera – twierdzenie kombinatoryczne w ekstremalnej teorii zbiorów, określające maksymalną liczność rodziny zbiorów, w której żaden zbiór nie jest podzbiorem innego. Twierdzenie to zostało sformułowane przez niemieckiego matematyka Emanuela Spernera w 1928 roku.

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 uporządkowanym przez zawieranie $\subseteq$ zbiorze potęgowym ${\mathcal {P}}(A)$ pewnego skończonego zbioru $A.$ Przykładem rodziny Spernera jest rodzina ${\mathcal {P}}_{k}(A)$wszystkich $k$-elementowych podzbiorów zbioru $A$ dla pewnego $k\leq n=|A|,$ której liczność wynosi $\textstyle {\binom {n}{k}}$.

Zgodnie z twierdzeniem Spernera jeśli ${\mathcal {F}}$ jest rodziną Spernera podzbiorów zbioru $n$-elementowego $A,$ to

$|{\mathcal {F}}|\leq {\binom {n}{\lfloor n/2\rfloor }}$.

Równoważnie rodzina ${\mathcal {P}}_{\lfloor n/2\rfloor }(A)$ jest antyłańcuchem w $({\mathcal {P}}(A),\subseteq )$ o maksymalnej liczbie elementów.

Dowód

Niech ${\mathcal {F}}=\{A_{1},A_{2},\dots ,A_{m}\}$ będzie rodziną Spernera podzbiorów zbioru $n$-elementowego $A$ i niech $a_{i}=|A_{i}|.$ Wówczas nierówność Lubella-Yamamoto-Meshalkina daje

$\sum _{i=1}^{m}{\frac {1}{\binom {n}{a_{i}}}}\leq 1$.

Ponieważ współczynniki dwumianowe spełniają nierówność

${\binom {n}{k}}\leq {\binom {n}{\lfloor n/2\rfloor }}$,

zachodzi

$1\geq \sum _{i=1}^{m}{\frac {1}{\binom {n}{a_{i}}}}\geq \sum _{i=1}^{m}{\frac {1}{\binom {n}{\lfloor n/2\rfloor }}}={\frac {m}{\binom {n}{\lfloor n/2\rfloor }}}$,

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 $n$-elementowego $A$ o maksymalnej liczności. Dla parzystych $n$ taka rodzina jest unikalna i jest nią ${\mathcal {P}}_{n/2}(A).$ Z kolei dla $n$ nieparzystych są dwie takie rodziny – ${\mathcal {P}}_{\lfloor n/2\rfloor }(A)$ oraz ${\mathcal {P}}_{\lceil n/2\rceil }(A)$.

Uogólnienie Bollobása (1965)

Niech podzbiory $A_{1},A_{2},\dots ,A_{m}$ oraz $B_{1},B_{2},\dots ,B_{m}$ zbioru $n$-elementowego $A$ spełniają warunek $A_{i}\cap B_{j}=\varnothing$ wtedy i tylko wtedy, gdy $i=j.$ Wówczas liczby $a_{i}=|A_{i}|$ oraz $b_{i}=|B_{i}|$ spełniają nierówność

$\sum _{i=1}^{m}{\frac {1}{\binom {a_{i}+b_{i}}{a_{i}}}}\leq 1$.

Twierdzenie Spernera otrzymamy, przyjmując $B_{i}=A\setminus A_{i}$.

Uogólnienie Erdősa (1945)

Niech ${\mathcal {F}}$ będzie rodziną podzbiorów zbioru $n$-elementowego $A.$ Jeśli nie istnieją różne zbiory $A_{0},A_{1},\dots ,A_{r}\in {\mathcal {F}},$ dla których $A_{0}\subseteq A_{1}\subseteq \dots \subseteq A_{r},$ to moc rodziny ${\mathcal {F}}$ jest nie większa od sumy $r$ największych współczynników dwumianowych $\textstyle {\binom {n}{k}}$. Twierdzenie Spernera stanowi tu przypadek $r=1.$

Zobacz też

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