Twierdzenie Dilwortha

Twierdzenie Dilwortha – 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.

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

Twierdzenie

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. 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}$ .

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

Dowód

Przedstawiony tu dowód indukcyjny podał Helge Tverberg w 1967 roku.

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

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

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.

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

Zastosowania

Twierdzenie Erdősa–Szekeresa

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

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ż

Przypisy

1 2 3 4 5 6 7 8 9 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 3 4 5 6 7 8 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.).
1 2 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.).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[:0-1] 1 2 3 4 5 6 7 8 9 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] 1 2 3 4 5 6 7 8 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] 1 2 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.).