Twierdzenie Spernera

Twierdzenie Spernera^[1][2] – 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^[1][2]. Twierdzenie to zostało sformułowane przez niemieckiego matematyka Emanuela Spernera w 1928 roku^[3].

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

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

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

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

Dowód^[1]

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

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

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

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

zachodzi

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

Uogólnienie Bollobása (1965)

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

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

Twierdzenie Spernera otrzymamy, przyjmując ${\displaystyle B_{i}=A\setminus A_{i}}$^[4].

Uogólnienie Erdősa (1945)

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

Zobacz też

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

Przypisy