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].

Twierdzenie edytuj

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

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

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

Dowód^[1]^[2] edytuj

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

Stosujemy indukcję względem mocy zbioru $X.$ Przypadek $|X|\leq 1$ jest oczywisty. Załóżmy teraz, że twierdzenie jest prawdziwe dla wszystkich zbiorów liczących mniej niż $n$ elementów. Przyjmijmy $|X|=n$ i niech $m$ będzie maksymalną licznością antyłańcucha w tym zbiorze, a $L$ dowolnym maksymalnym (czyli takim, którego nie można powiększyć) łańcuchem. Oczywiście zbioru $X$ nie możemy pokryć mniej niż $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 $X\setminus L$ ma co najwyżej $m-1$ elementów, to na mocy założenia indukcyjnego $X$ jest sumą łańcucha $L$ oraz $m-1$ łańcuchów, które pokrywają $X\setminus L.$

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

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

,

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

.

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

G=G_{1}\cup G_{2}\cup \dots \cup G_{m}

,

D=D_{1}\cup D_{2}\cup \dots \cup D_{m}

.

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

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

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

Twierdzenie dualne edytuj

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].

Zastosowania edytuj

Twierdzenie Erdősa–Szekeresa^[2] edytuj

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

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

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

Podciąg $(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 $A$ i nierosnący, gdy zbiór ten tworzy antyłańcuch. Jeśli najliczniejszy antyłańcuch w $A$ ma co najmniej $m+1$ elementów, to natychmiast otrzymujemy tezę. W przeciwnym wypadku zbiór $A$ jest sumą $m$ łańcuchów. Wówczas na mocy zasady szufladkowej Dirichleta istnieje łańcuch o mocy nie mniejszej niż $\textstyle {\frac {nm+1}{m}}=n+{\frac {1}{m}},$ czyli co najmniej $n+1.$ To kończy dowód.

Rozkład zbioru potęgowego na sumę łańcuchów^[1] edytuj

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

Zobacz też edytuj

Przypisy edytuj

↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ WitoldW. Lipski WitoldW., WiktorW. Marek WiktorW., Analiza kombinatoryczna, t. 59, Państwowe Wydawnictwo Naukowe, 1986, s. 178-189, ISBN 978-83-01-04972-0 (pol.).
↑ ^a ^b ^c ^d ^e ^f ^g ^h BeataB. Bogdańska BeataB., AdamA. Neugebauer AdamA., Kombinatoryka, Wydawnictwo Szkolne OMEGA, 2018 (Matematyka Olimpijska), s. 68-72, ISBN 978-83-7267-712-9 (pol.).
↑ R.P.R.P. Dilworth R.P.R.P., A Decomposition Theorem for Partially Ordered Sets, „Annals of Mathematics”, 51 (1), 1950, s. 161–166, DOI: 10.2307/1969503, ISSN 0003-486X, JSTOR: 1969503 (ang.).
↑ EgbertE. Harzheim EgbertE., Ordered Sets, t. 7, Advances in Mathematics, New York: Springer, 2005, s. 60, ISBN 978-0-387-24219-4 [dostęp 2024-02-25] (ang.).
↑ HelgeH. Tverberg HelgeH., On Dilworth's Decomposition Theorem for Partially Ordered Sets, „Journal of Combinatorial Theory”, 3, 1967, s. 305-306 [dostęp 2024-02-25] (ang.).
↑ ^a ^b LeonL. Mirsky LeonL., A Dual of Dilworth's Decomposition Theorem, „The American Mathematical Monthly”, 78 (8), 1971, s. 876-877, DOI: 10.2307/2316481, JSTOR: 2316481 (ang.).

[:0-1] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ WitoldW. Lipski WitoldW., WiktorW. Marek WiktorW., Analiza kombinatoryczna, t. 59, Państwowe Wydawnictwo Naukowe, 1986, s. 178-189, ISBN 978-83-01-04972-0 (pol.).

[:1-2] ↑ ^a ^b ^c ^d ^e ^f ^g ^h BeataB. Bogdańska BeataB., AdamA. Neugebauer AdamA., Kombinatoryka, Wydawnictwo Szkolne OMEGA, 2018 (Matematyka Olimpijska), s. 68-72, ISBN 978-83-7267-712-9 (pol.).

[3] R.P.R.P. Dilworth R.P.R.P., A Decomposition Theorem for Partially Ordered Sets, „Annals of Mathematics”, 51 (1), 1950, s. 161–166, DOI: 10.2307/1969503, ISSN 0003-486X, JSTOR: 1969503 (ang.).

[4] EgbertE. Harzheim EgbertE., Ordered Sets, t. 7, Advances in Mathematics, New York: Springer, 2005, s. 60, ISBN 978-0-387-24219-4 [dostęp 2024-02-25] (ang.).

[5] HelgeH. Tverberg HelgeH., On Dilworth's Decomposition Theorem for Partially Ordered Sets, „Journal of Combinatorial Theory”, 3, 1967, s. 305-306 [dostęp 2024-02-25] (ang.).

[:2-6] LeonL. Mirsky LeonL., A Dual of Dilworth's Decomposition Theorem, „The American Mathematical Monthly”, 78 (8), 1971, s. 876-877, DOI: 10.2307/2316481, JSTOR: 2316481 (ang.).

[1]

[2]

[3]

[4]

[5]

[6]