Twierdzenie Spernera

Twierdzenie Spernera w matematyce dyskretnej opisuje największe możliwe rodziny zbiorów skończonych , z których żaden nie zawiera żadnych innych zbiorów w rodzinie. Jest to jeden z centralnych rezultatów teorii mnogości ekstremalnej . Jej nazwa pochodzi od nazwiska Emanuela Spernera , który opublikował ją w 1928 roku.

Ten wynik jest czasami nazywany lematem Spernera, ale nazwa „ lemat Spernera ” odnosi się również do niezwiązanego wyniku kolorowania triangulacji. Aby rozróżnić te dwa wyniki, wynik dotyczący wielkości rodziny Spernera jest obecnie bardziej znany jako twierdzenie Spernera.

Oświadczenie

Rodzina zbiorów , w której żaden ze zbiorów nie jest ścisłym podzbiorem innego, nazywana jest rodziną Spernera , antyłańcuchem zbiorów lub bałaganem. Na przykład rodzina k -elementowych podzbiorów zbioru n -elementowego jest rodziną Spernera. Żaden zestaw w tej rodzinie nie może zawierać żadnego innego, ponieważ zbiór zawierający musi być większy niż zbiór, który zawiera, aw tej rodzinie wszystkie zbiory mają taką samą wielkość. Wartość k , która sprawia, że ten przykład ma jak najwięcej zestawów, wynosi n /2, jeśli n jest parzysta lub jedna z liczb całkowitych najbliższych n /2, jeśli n jest nieparzyste. Dla tego wyboru liczba zestawów w rodzinie wynosi ${\ Displaystyle {\ tbinom {n} {\ lfloor n/2 \ rfloor}}}$ .

Twierdzenie Spernera stwierdza, że te przykłady są największymi możliwymi rodzinami Spernera w zbiorze n -elementowym. Formalnie twierdzenie stwierdza, że

dla każdej rodziny Spernerów S , której związek ma łącznie n elementów, ${\ Displaystyle | S | \ leq {\ binom {n} {\ lfloor n/2 \ rfloor}},}$ i
równość zachodzi wtedy i tylko wtedy, gdy S składa się $lceil n/2\rceil }$ wszystkich podzbiorów zbioru n -elementów mają $\$ lub wszystkie, które mają rozmiar ${\ Displaystyle$ .

Zamówienia częściowe

Twierdzenie Spernera można również wyrazić w kategoriach częściowej szerokości rzędu . Rodzina wszystkich podzbiorów n -elementowego (jego zbiór potęgowy ) może być częściowo uporządkowana przez włączenie zbioru; w tym częściowym porządku mówi się, że dwa różne elementy są nieporównywalne, gdy żaden z nich nie zawiera drugiego. Szerokość częściowego porządku to największa liczba elementów w antyłańcuchu , zbiór elementów nieporównywalnych parami. Przekładając tę terminologię na język zbiorów, antyłańcuch to po prostu rodzina Spernera, a szerokość częściowego porządku to maksymalna liczba zbiorów w rodzinie Spernera. Zatem innym sposobem wyrażenia twierdzenia Spernera jest to, że szerokość rzędu inkluzji w zbiorze potęg wynosi ${\ Displaystyle {\ binom {n} {\ lfloor n/2 \ rfloor}}}$ .

że częściowo uporządkowany zbiór stopniowany ma właściwość Spernera , gdy jeden z jego największych antyłańcuchów jest utworzony przez zbiór elementów, które mają tę samą rangę. W tej terminologii twierdzenie Spernera stwierdza, że częściowo uporządkowany zbiór wszystkich podzbiorów zbioru skończonego, częściowo uporządkowany przez włączenie zbioru, ma właściwość Spernera.

Dowód

Istnieje wiele dowodów twierdzenia Spernera, z których każdy prowadzi do różnych uogólnień (patrz Anderson (1987) ).

Poniższy dowód pochodzi od Lubella (1966) . Niech s _k oznacza liczbę k -zbiorów w S . dla wszystkich 0 ≤ k ≤ n ,

{\ Displaystyle {n \ wybierz \ lfloor {n/2} \ rfloor} \ geq {n \ wybierz k}}

a zatem,

{\ Displaystyle {s_ {k} \ ponad {n \ wybierz \ lfloor {n/2} \ rfloor}} \ równoważnik {s_ {k} \ ponad {n \ wybierz k}}.}

Ponieważ S jest antyłańcuchem, możemy zsumować powyższą nierówność od k = 0 do n , a następnie zastosować nierówność LYM , aby otrzymać

{\ Displaystyle \ suma _ {k = 0} ^ {n} {s_ {k} \ ponad {n \choose \lfloor {n/2}\rfloor}}\leq \sum _{k=0}^{n}{s_{k} \over {n \choose k}}\leq 1,}

co znaczy

{\ Displaystyle | S | = \ suma _ {k = 0} ^ {n} s_ {k} \ równoważnik {n \ wybierz \ lfloor {n/2} \ rfloor}.}

To kończy dowód części 1.

Aby mieć równość, wszystkie nierówności w poprzednim dowodzie muszą być równościami. Od

{\ Displaystyle {n \ wybierz \ lfloor {n/2} \ rfloor} = {n \ wybierz k}}

wtedy i tylko wtedy, gdy ${\ Displaystyle k = \ lfloor {n/2} \ rfloor}$ lub ${\ Displaystyle \ lceil {n/2} \ rceil,}$ wnioskujemy, że równość oznacza, że S składa się tylko z zestawów rozmiarów lub ${\ Displaystyle \ lceil {n/2} \ rceil.}$ $n / 2 ⌋ {\ displaystyle \ lfloor {$ Nawet n , co kończy dowód części 2.

W przypadku nieparzystego n jest więcej pracy do wykonania, którą tutaj pomijamy, ponieważ jest skomplikowana. Patrz Anderson (1987) , s. 3–4.

Uogólnienia

$uogólnień$ kilka Spernera dla podzbiorów wszystkich .

Bez długich łańcuchów

Łańcuch to podrodzina { $\ Displaystyle \ {S_ {0}, S_ {1}, \ kropki, S_ {r} \} \ subseteq {\ mathcal {P}} (E)}$ , który jest całkowicie uporządkowany, tj. ${\ Displaystyle S_ {0} \ podzbiór S_ {1} \ podzbiór \ kropki \ podzbiór S_ {r}}$ (prawdopodobnie po przenumerowaniu). Łańcuch ma r + 1 członków i długość r . Rodzina bez łańcuchów r (zwana także rodziną r ) to rodzina podzbiorów E , która nie zawiera łańcucha o długości r . Erdős (1945) udowodnił, że największy rozmiar rodziny bez łańcuchów r jest sumą r największych współczynników dwumianowych ${\ Displaystyle {\ binom {n} {i}}}$ . Przypadek r = 1 jest twierdzeniem Spernera.

p -kompozycje zestawu

$p}}$ mi p - krotek podzbiorów E , mówimy p - krotka ${\ Displaystyle (S_ {1}, \ kropki, S_ {p})}$ jest ≤ inny, ${\ Displaystyle (T_ {1}, \ kropki, T_ {p}) ,}$ jeśli ${\ Displaystyle S_ {i} \ subseteq T_ {i}}$ dla każdego ja = 1,2, ..., p . Nazywamy ${\ Displaystyle (S_ {1}, \ kropki, S_ {p})}$ p -kompozycję E , jeśli zbiory ${\ Displaystyle S_ { 1},\kropki ,S_{p}}$ tworzą partycję E . Meszalkin (1963) udowodnił, że maksymalny rozmiar antyłańcucha p -kompozycji to największy p -współczynnik wielomianowy ${\ Displaystyle {\ binom {n} {n_ {1} \ n_ {2} \ \dots \ n_{p}}},}$ czyli współczynnik, w którym wszystkie n _i są tak bliskie, jak to tylko możliwe (tj. różnią się co najwyżej o 1). Meshalkin udowodnił to, udowadniając uogólnioną nierówność LYM.

Przypadek p = 2 jest twierdzeniem Spernera, ponieważ wtedy założenia redukują się do zbiorów $= E \ setminus S_ {1}$ $} }$ będąc rodziną Spernerów.

Brak długich łańcuchów w p -składach zbioru

Beck i Zaslavsky (2002) połączyli twierdzenia Erdösa i Meshalkina, dostosowując dowód Meshalkina na jego uogólnioną nierówność LYM. Pokazali, że największy rozmiar rodziny p -składów taki, że zbiory na i -tej pozycji p -krotek , pomijając duplikacje, są r -bezłańcuchowe, dla każdego ${\ Displaystyle i = 1,2, \ kropki, p-1}$ (ale niekoniecznie dla i = p większa $-$ suma wielomianowych współczynników

Rzutowy analog geometrii

W skończonej geometrii rzutowej PG ( re , fa _q ) wymiaru d nad skończonym polem rzędu q , niech ${\ Displaystyle {\ mathcal {L}} (p, F_ {q})}$ będzie rodziną wszystkich podprzestrzeni. W przypadku częściowego uporządkowania przez włączenie zbioru ta rodzina jest kratą. Rota i Harper (1971) udowodnili, że największy rozmiar antyłańcucha w ${\ Displaystyle {\ mathcal {L}} (p, F_ {q})}$ to największy współczynnik Gaussa ${\ Displaystyle {\ rozpocząć {bmatrix} d + 1 \\ k \ koniec {bmatrix}};}$ to jest analog geometrii rzutowej lub q -analog twierdzenia Spernera.

Ponadto udowodnili, że największy rozmiar rodziny bez łańcuchów r w $L}} (p, F_ {q})$ { } współczynniki. Ich dowodem jest rzutowy analog nierówności LYM.

Brak długich łańcuchów w p -składach przestrzeni rzutowej

Beck i Zaslavsky (2003) uzyskali podobne do Meshalkina uogólnienie twierdzenia Roty – Harpera. W PG ( re , fa _q ) sekwencja Meshalkina o długości p jest sekwencją podprzestrzeni rzutowych takich, że ${\ Displaystyle (A_ {1}, \ ldots, A_ {p})}$ żadna właściwa podprzestrzeń PG( d , F _q ) nie zawiera ich wszystkich, a ich wymiary sumują się do ${\ displaystyle dp + 1}$ . Twierdzenie jest takie, że rodzina ciągów Meshalkina o długości p w PG( d , F _q ), taka, że podprzestrzenie pojawiające się na pozycji i ciągów nie zawierają łańcucha o długości r dla każdego ${\ Displaystyle i = 1,2, \ kropki, p-1,}$ jest nie więcej niż sumą największego ${\ displaystyle r ^ {p-1}}$ ilości

{\ Displaystyle {\ rozpocząć {bmatrix} d + 1 \\ n_ {1} \ n_ {2} \ \ kropki \ n_{p}\end{bmacierz}}q^{s_{2}(n_{1},\ldots,n_{p})},}

gdzie ${\ Displaystyle {\ rozpocząć {bmatrix} d + 1 \\ n_ {1} \ n_ {2} \ \ kropki \ n_ {p} \ koniec {bmatrix}} }$ $_$ zakładamy _ _ _

{\ Displaystyle {\ rozpocząć {bmatrix} d + 1 \ \n_{1}\end{bmatrix}}{\begin{bmatrix}d+1-n_{1}\\n_{2}\end{bmatrix}}\cdots {\begin{bmatrix}d+1-( n_{1}+\cdots +n_{p-1})\\n_{p}\end{bmacierz}}}

I

{\ Displaystyle s_ {2} ( n_{1},\ldots ,n_{p}):=n_{1}n_{2}+n_{1}n_{3}+n_{2}n_{3}+n_{1}n_{4} +\cdots +n_{p-1}n_{p},}

druga elementarna funkcja symetryczna liczb ${\ Displaystyle n_ {1}, n_ {2}, \ kropki, n_ {p}.}$

Zobacz też

Anderson, Ian (1987), Kombinatoryka zbiorów skończonych , Oxford University Press .
Beck, Maciej; Zaslavsky, Thomas (2002), „Krótszy, prostszy, silniejszy dowód ograniczeń Meshalkina-Hochberga-Hirscha na składowych antyłańcuchach”, Journal of Combinatorial Theory , Seria A, 100 (1): 196–199, arXiv : math / 0112068 , doi : 10.1006/jcta.2002.3295 , MR 1932078 , S2CID 8136773 .
Beck, Maciej; Zaslavsky, Thomas (2003), „Twierdzenie Meshalkina dla geometrii rzutowych”, Journal of Combinatorial Theory , Seria A, 102 (2): 433–441, arXiv : math / 0112069 , doi : 10.1016 / S0097-3165 (03) 00049 -9 , MR 1979545 , S2CID 992137 .
Engel, Konrad (1997), Teoria Spernera , Encyklopedia matematyki i jej zastosowań, tom. 65, Cambridge: Cambridge University Press, s. x+417, doi : 10.1017/CBO9780511574719 , ISBN 0-521-45206-6 , MR 1429390 .
Engel, K. (2001) [1994], „Twierdzenie Spernera” , Encyklopedia matematyki , EMS Press
Erdős, P. (1945), „O lemacie Littlewooda i Offorda” (PDF) , Biuletyn Amerykańskiego Towarzystwa Matematycznego , 51 (12): 898–902, doi : 10.1090 / S0002-9904-1945-08454-7 , MR 0014608
Lubell, D. (1966), „Krótki dowód lematu Spernera”, Journal of Combinatorial Theory , 1 (2): 299, doi : 10.1016/S0021-9800 (66) 80035-2 , MR 0194348 .
Meshalkin, LD (1963), „Uogólnienie twierdzenia Spernera o liczbie podzbiorów zbioru skończonego”, Teoria prawdopodobieństwa i jego zastosowania (w języku rosyjskim), 8 (2): 203–204, doi : 10.1137/1108023 .
Rota, Gian-Carlo ; Harper, LH (1971), „Teoria dopasowywania, wprowadzenie”, Postępy w prawdopodobieństwie i tematy pokrewne, tom. 1 , Nowy Jork: Dekker, s. 169–215, MR 0282855 .
Sperner, Emanuel (1928), „Ein Satz über Untermengen einer endlichen Menge”, Mathematische Zeitschrift (w języku niemieckim), 27 (1): 544–548, doi : 10.1007/BF01171114 , hdl : 10338.dmlcz/127405 , JFM 54.0090. 06 , S2CID 123451223 .

Linki zewnętrzne

Twierdzenie Spernera przy przecięciu węzła
Twierdzenie Spernera na wiki polymath1