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 $𝒫(A)$ pewnego skończonego zbioru $A.$ Przykładem rodziny Spernera jest rodzina ${𝒫}_k(A)$wszystkich $k$-elementowych podzbiorów zbioru $A$ dla pewnego $k\le n=|A|,$ której liczność wynosi $(\genfrac{}{}{0ex}{}{n}{k})$.

Zgodnie z twierdzeniem Spernera jeśli $ℱ$ jest rodziną Spernera podzbiorów zbioru $n$-elementowego $A,$ toSzablon:WzórRównoważnie rodzina ${𝒫}_{\lfloor n/2\rfloor }(A)$ jest antyłańcuchem w $(𝒫(A),\subseteq )$ o maksymalnej liczbie elementów.

Dowód

Niech $ℱ=\{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 Szablon:Wzór

Ponieważ współczynniki dwumianowe spełniają nierówność Szablon:Wzór zachodzi Szablon:Wzór 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ą ${𝒫}_{n/2}(A).$ Z kolei dla $n$ nieparzystych są dwie takie rodziny – ${𝒫}_{\lfloor n/2\rfloor }(A)$ oraz ${𝒫}_{\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ść Szablon:Wzór Twierdzenie Spernera otrzymamy, przyjmując $B_i=A\setminus A_i$.

Uogólnienie Erdősa (1945)

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

Zobacz też

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