Twierdzenie Dilwortha

Twierdzenie Dilwortha^[1][2] – twierdzenie kombinatoryczne o charakterze minimaksowym dotyczące struktury zbiorów częściowo uporządkowanych. Zgodnie z twierdzeniem Dilwortha w dowolnym skończonym zbiorze częściowo uporządkowanym maksymalna liczność antyłańcucha jest równa minimalnej liczbie łańcuchów, które pokrywają ten zbiór^[1][2].

Twierdzenie to zostało sformułowane przez amerykańskiego matematyka Roberta Dilwortha, który opublikował jego dowód w 1950 roku^[3].

 Zobacz też: Łańcuch i Antyłańcuch.

Niech ${\displaystyle \preccurlyeq }$ będzie relacją częściowego porządku na zbiorze ${\displaystyle X}$. Łańcuchem nazywa się zbiór ${\displaystyle L\subseteq X,}$ w którym każde dwa elementy są porównywalne, czyli zbiór ${\displaystyle L}$ jest uporządkowany liniowo przez relację ${\displaystyle \preccurlyeq .}$ Z kolei podzbiór ${\displaystyle A\subseteq X,}$ w którym każde dwa elementy są nieporównywalne, nazywa się antyłańcuchem^[2]. Minimalna liczba łańcuchów, które pokrywają zbiór ${\displaystyle X,}$ to najmniejsza taka liczba całkowita ${\displaystyle n,}$ że istnieją łańcuchy ${\displaystyle L_{1},L_{2},\dots ,L_{n}\subseteq X,}$ dla których zachodzi ${\displaystyle X=L_{1}\cup L_{2}\cup \dots \cup L_{n}}$^[1].

Twierdzenie Dilwortha orzeka, że jeśli zbiór ${\displaystyle X}$ jest skończony, to maksymalna liczność (moc) antyłańcucha jest równa minimalnej liczbie łańcuchów, które pokrywają zbiór ${\displaystyle X}$^[1][2]. Twierdzenie to jest prawdziwe również, gdy zbiór ${\displaystyle X}$ jest nieskończony, ale maksymalna moc antyłańcucha w tym zbiorze jest skończona^[4].

Przedstawiony tu dowód indukcyjny podał Helge Tverberg w 1967 roku^[5].

Stosujemy indukcję względem mocy zbioru ${\displaystyle X.}$ Przypadek ${\displaystyle |X|\leq 1}$ jest oczywisty. Załóżmy teraz, że twierdzenie jest prawdziwe dla wszystkich zbiorów liczących mniej niż ${\displaystyle n}$ elementów. Przyjmijmy ${\displaystyle |X|=n}$ i niech ${\displaystyle m}$ będzie maksymalną licznością antyłańcucha w tym zbiorze, a ${\displaystyle L}$ dowolnym maksymalnym (czyli takim, którego nie można powiększyć) łańcuchem. Oczywiście zbioru ${\displaystyle X}$ nie możemy pokryć mniej niż ${\displaystyle m}$ łańcuchami, ponieważ każdy łańcuch może zawierać co najwyżej jeden element antyłańcucha.

Jeśli każdy antyłańcuch w zbiorze ${\displaystyle X\setminus L}$ ma co najwyżej ${\displaystyle m-1}$ elementów, to na mocy założenia indukcyjnego ${\displaystyle X}$ jest sumą łańcucha ${\displaystyle L}$ oraz ${\displaystyle m-1}$ łańcuchów, które pokrywają ${\displaystyle X\setminus L.}$

Załóżmy zatem, że w ${\displaystyle X\setminus L}$ istnieje antyłańcuch ${\displaystyle m}$-elementowy ${\displaystyle A=\{a_{1},a_{2},\dots ,a_{m}\}.}$ Ponieważ każdy antyłańcuch w ${\displaystyle X\setminus L}$ jest też antyłańcuchem w ${\displaystyle X,}$ antyłańcuch ${\displaystyle A}$ jest maksymalnej liczności. Utwórzmy zbiory

${\displaystyle G=\{x\in P\;\colon \,\exists a\in A\colon x\succcurlyeq a\}}$,

${\displaystyle D=\{x\in P\;\colon \,\exists a\in A\colon x\preccurlyeq a\}}$.

Niech ${\displaystyle c}$ będzie najmniejszym elementem łańcucha ${\displaystyle L.}$ Oczywiście ${\displaystyle c\not \in G}$ – w przeciwnym wypadku łańcuch ${\displaystyle L}$ można by powiększyć. Analogicznie ${\displaystyle D}$ nie zawiera największego elementu ${\displaystyle L.}$ Stąd ${\displaystyle |G|<|X|}$ oraz ${\displaystyle |D|<|X|}$ i na mocy założenia indukcyjnego istnieją rozkłady na łańcuchy

${\displaystyle G=G_{1}\cup G_{2}\cup \dots \cup G_{m}}$,

${\displaystyle D=D_{1}\cup D_{2}\cup \dots \cup D_{m}}$.

Bez straty ogólności niech ${\displaystyle a_{i}\in G_{i}}$ oraz ${\displaystyle a_{i}\in D_{i}.}$ Jeśli ${\displaystyle a_{i}}$ nie jest najmniejszym elementem ${\displaystyle G_{i},}$ to dla pewnych ${\displaystyle x\in G_{i},}$ ${\displaystyle a\in A}$ zachodzi ${\displaystyle a\preccurlyeq x\preccurlyeq a_{i},}$ co jest sprzeczne z definicją antyłańcucha. Analogicznie dowodzi się, że ${\displaystyle a_{i}}$ jest największym elementem ${\displaystyle D_{i}.}$ Zauważmy, że ${\displaystyle X=G\cup D,}$ ponieważ w przeciwnym wypadku antyłańcuch ${\displaystyle A}$ można by powiększyć o pewien element ${\displaystyle x\in X\setminus (G\cup D).}$ Stąd

${\displaystyle X=(D_{1}\cup G_{1})\cup (D_{2}\cup G_{2})\cup \dots \cup (D_{m}\cup G_{m})}$

jest rozkładem zbioru ${\displaystyle X}$ na ${\displaystyle m}$ łańcuchów. Wobec dowolności zbioru ${\displaystyle X}$ teza zachodzi dla wszystkich zbiorów o mocy ${\displaystyle n,}$ co kończy dowód indukcyjny.

Twierdzenie Dilwortha pozostaje prawdziwe, gdy w jego sformułowaniu zamienimy miejscami sformułowania „łańcuch” i „antyłańcuch”^[1]. Taką postać twierdzenia nazywa się dualnym twierdzeniem Dilwortha^[1][2]. Dowód tego twierdzenia przedstawił Leon Mirsky w 1971 roku^[6].

Dualne twierdzenie Dilwortha orzeka, że w dowolnym skończonym zbiorze częściowo uporządkowanym maksymalna liczność łańcucha jest równa minimalnej liczbie antyłańcuchów, które pokrywają ten zbiór^[1][2].

Podobnie jak twierdzenie Dilwortha, twierdzenie dualne jest prawdziwe również dla zbiorów nieskończonych pod warunkiem, że maksymalna liczność łańcucha jest ograniczona^[6].

Każdy ciąg liczb rzeczywistych o ${\displaystyle nm+1}$ wyrazach zawiera podciąg niemalejący długości ${\displaystyle n+1}$ lub podciąg nierosnący długości ${\displaystyle m+1.}$

Niech ${\displaystyle (a_{1},a_{2},\dots ,a_{nm+1})}$ będzie dowolnym takim ciągiem. Wprowadźmy w zbiorze ${\displaystyle A=\{(k,a_{k})\;\colon \,1\leq k\leq nm+1\}}$ relację

${\displaystyle (i,a_{i})\preccurlyeq (j,a_{j})\iff i\leq j\land a_{i}\leq a_{j}.}$

Podciąg ${\displaystyle (a_{k_{1}},a_{k_{2}},\dots ,a_{k_{l}})}$ jest niemalejący wtedy i tylko wtedy, gdy odpowiadający mu zbiór par tworzy łańcuch w ${\displaystyle A}$ i nierosnący, gdy zbiór ten tworzy antyłańcuch. Jeśli najliczniejszy antyłańcuch w ${\displaystyle A}$ ma co najmniej ${\displaystyle m+1}$ elementów, to natychmiast otrzymujemy tezę. W przeciwnym wypadku zbiór ${\displaystyle A}$ jest sumą ${\displaystyle m}$ łańcuchów. Wówczas na mocy zasady szufladkowej Dirichleta istnieje łańcuch o mocy nie mniejszej niż ${\displaystyle \textstyle {\frac {nm+1}{m}}=n+{\frac {1}{m}},}$ czyli co najmniej ${\displaystyle n+1.}$ To kończy dowód.

Rozważmy ${\displaystyle ({\mathcal {P}}(A),\subseteq )}$ – rodzinę wszystkich podzbiorów zbioru ${\displaystyle A}$ uporządkowaną przez relację zawierania. Twierdzenie Spernera mówi, że najliczniejszy antyłańcuch w tym zbiorze ma ${\displaystyle \textstyle {\binom {n}{\lfloor n/2\rfloor }}}$ elementów. Z twierdzenia Dilwortha wynika, że ${\displaystyle {\mathcal {P}}(A)}$ można przedstawić jako sumę ${\displaystyle \textstyle {\binom {n}{\lfloor n/2\rfloor }}}$ łańcuchów. Ponadto jest to najmniejsza liczba o tej własności.

• twierdzenie Spernera
• częściowy porządek
• krata