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 $\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}}$ ^[1].

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

|{\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^[2].

Dowód^[1]

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)$ ^[4].

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}$ ^[4].

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}}$ ^[5]. Twierdzenie Spernera stanowi tu przypadek $r=1.$

Zobacz też

Przypisy

↑ ^a ^b ^c ^d ^e WitoldW. Lipski WitoldW., WiktorW. Marek WiktorW., Analiza kombinatoryczna, t. 59, Państwowe Wydawnictwo Naukowe, 1986 (Biblioteka Matematyczna), s. 188-189, ISBN 978-83-01-04972-0 (pol.).
↑ ^a ^b ^c ^d BeataB. Bogdańska BeataB., AdamA. Neugebauer AdamA., Kombinatoryka, Wydawnictwo Szkolne OMEGA, 2018 (Matematyka Olimpijska), s. 72-73, ISBN 978-83-7267-712-9 (pol.).
↑ EmanuelE. Sperner EmanuelE., Ein Satz über Untermengen einer endlichen Menge, „Mathematische Zeitschrift”, 27, 1928, s. 544–548, ISSN 0025-5874 [dostęp 2024-02-28] (niem.).
↑ ^a ^b IanI. Anderson IanI., Combinatorics of finite sets, Oxford University Press, 1989, s. 3-5, ISBN 978-0-19-853367-2 (ang.).
↑ PaulP. Erdős PaulP., On a lemma of Littlewood and Offord, „Bulletin of the American Mathematical Society”, 51 (12), 1945, s. 898–902, DOI: 10.1090/S0002-9904-1945-08454-7, ISSN 0002-9904 [dostęp 2024-02-28] (ang.).

[:0-1] WitoldW. Lipski WitoldW., WiktorW. Marek WiktorW., Analiza kombinatoryczna, t. 59, Państwowe Wydawnictwo Naukowe, 1986 (Biblioteka Matematyczna), s. 188-189, ISBN 978-83-01-04972-0 (pol.).

[:1-2] BeataB. Bogdańska BeataB., AdamA. Neugebauer AdamA., Kombinatoryka, Wydawnictwo Szkolne OMEGA, 2018 (Matematyka Olimpijska), s. 72-73, ISBN 978-83-7267-712-9 (pol.).

[3] EmanuelE. Sperner EmanuelE., Ein Satz über Untermengen einer endlichen Menge, „Mathematische Zeitschrift”, 27, 1928, s. 544–548, ISSN 0025-5874 [dostęp 2024-02-28] (niem.).

[:2-4] IanI. Anderson IanI., Combinatorics of finite sets, Oxford University Press, 1989, s. 3-5, ISBN 978-0-19-853367-2 (ang.).

[5] PaulP. Erdős PaulP., On a lemma of Littlewood and Offord, „Bulletin of the American Mathematical Society”, 51 (12), 1945, s. 898–902, DOI: 10.1090/S0002-9904-1945-08454-7, ISSN 0002-9904 [dostęp 2024-02-28] (ang.).

[1]

[2]

[3]

[4]

[5]