Dilworthova věta - Dilworths theorem - Wikipedia

v matematika v oblastech teorie objednávek a kombinatorika, Dilworthova věta charakterizuje šířka jakékoli konečné částečně objednaná sada ve smyslu a rozdělit objednávky na minimální počet řetězy. Je pojmenován pro matematika Robert P. Dilworth  (1950 ).

An antichain v částečně uspořádané sadě je sada prvků, z nichž dva nejsou navzájem srovnatelné, a řetězec je sada prvků, z nichž každé dva jsou srovnatelné. Řetězový rozklad je rozdělení prvků řádu do disjunktní řetězy. Dilworthova věta uvádí, že v každé konečné částečně uspořádané množině má největší antichain stejnou velikost jako nejmenší řetězový rozklad. Zde je velikost antichainu počet jeho prvků a velikost rozkladu řetězce je jeho počet řetězců. Šířka dílčího řádu je definována jako běžná velikost antichainového a řetězového rozkladu.

Verze věty pro nekonečné částečně uspořádané množiny uvádí, že když existuje rozklad na konečně mnoho řetězců, nebo když existuje konečná horní mez na velikosti antichainu, velikosti největší antichainu a nejmenšího řetězce rozkladu jsou si opět rovni.

Induktivní důkaz

Následující důkaz indukcí velikosti částečně objednané sady ${ displaystyle P}$ je založen na tom z Galvin  (1994 ).

Nechat ${ displaystyle P}$ být konečnou částečně objednanou množinou. Věta platí triviálně, pokud ${ displaystyle P}$ je prázdný. Předpokládejme to ${ displaystyle P}$ má alespoň jeden prvek a let ${ displaystyle a}$ být maximálním prvkem ${ displaystyle P}$.

Indukcí předpokládáme, že pro celé číslo ${ displaystyle k}$ částečně objednaná sada ${ displaystyle P ': = P setminus {a }}$ může být pokryta ${ displaystyle k}$ disjunktní řetězy ${ displaystyle C_ {1}, tečky, C_ {k}}$ a má alespoň jeden antichain ${ displaystyle A_ {0}}$ velikosti ${ displaystyle k}$. Jasně, ${ displaystyle A_ {0} čepice C_ {i} neq emptyset}$ pro ${ displaystyle i = 1,2, tečky, k}$. Pro ${ displaystyle i = 1,2, tečky, k}$, nechť ${ displaystyle x_ {i}}$ být maximálním prvkem v ${ displaystyle C_ {i}}$ který patří do antichain velikosti ${ displaystyle k}$ v ${ displaystyle P '}$a nastavit ${ displaystyle A: = {x_ {1}, x_ {2}, dots, x_ {k} }}$. Tvrdíme to ${ displaystyle A}$ je antichain. Nechat ${ displaystyle A_ {i}}$ být antichain velikosti ${ displaystyle k}$ který obsahuje ${ displaystyle x_ {i}}$. Opravte libovolné odlišné indexy ${ displaystyle i}$ a ${ displaystyle j}$. Pak ${ displaystyle A_ {i} čepice C_ {j} neq emptyset}$. Nechat ${ displaystyle y v A_ {i} čepici C_ {j}}$. Pak ${ displaystyle y leq x_ {j}}$, podle definice ${ displaystyle x_ {j}}$. To z toho vyplývá ${ displaystyle x_ {i} ne geq x_ {j}}$, od té doby ${ displaystyle x_ {i} ne geq y}$. Výměnou rolí ${ displaystyle i}$ a ${ displaystyle j}$ v tomto argumentu také máme ${ displaystyle x_ {j} ne geq x_ {i}}$. Tím se to ověří ${ displaystyle A}$ je antichain.

Nyní se vracíme do ${ displaystyle P}$. Předpokládejme, že první ${ displaystyle a geq x_ {i}}$ pro některé ${ displaystyle i in {1,2, tečky, k }}$. Nechat ${ displaystyle K}$ být řetězem ${ displaystyle {a } pohár {z v C_ {i}: z leq x_ {i} }}$. Pak výběrem ${ displaystyle x_ {i}}$, ${ displaystyle P setminus K}$ nemá antichain velikosti ${ displaystyle k}$. Indukce to tedy naznačuje ${ displaystyle P setminus K}$ může být pokryta ${ displaystyle k-1}$ disjunktní řetězy od ${ displaystyle A setminus {x_ {i} }}$ je antichain velikosti ${ displaystyle k-1}$ v ${ displaystyle P setminus K}$. Tím pádem, ${ displaystyle P}$ může být pokryta ${ displaystyle k}$ disjunktní řetězy podle potřeby. Dále, pokud ${ displaystyle a ne geq x_ {i}}$ pro každého ${ displaystyle i in {1,2, tečky, k }}$, pak ${ displaystyle A cup {a }}$ je antichain velikosti ${ displaystyle k + 1}$ v ${ displaystyle P}$ (od té doby ${ displaystyle a}$ je maximální v ${ displaystyle P}$). Nyní ${ displaystyle P}$ mohou být pokryty ${ displaystyle k + 1}$ řetězy ${ displaystyle {a }, C_ {1}, C_ {2}, tečky, C_ {k}}$, vyplnění důkazu.

Důkaz přes Kőnigovu větu

Důkaz Dilworthovy věty pomocí Kőnigovy věty: konstrukce bipartitního grafu z dílčího řádu a rozdělení do řetězců podle shody

Stejně jako řada dalších výsledků v kombinatorice je Dilworthova věta ekvivalentní Kőnigova věta na bipartitní graf shoda a několik dalších souvisejících vět včetně Hallova věta o manželství (Fulkerson 1956 ).

Prokázat Dilworthovu větu pro částečnou objednávku S s n prvky pomocí Kőnigovy věty definují bipartitní graf G = (U,PROTI,E) kde U = PROTI = S a kde (u,proti) je hrana v G když u < proti v S. Podle Kőnigovy věty existuje shoda M v Ga sada vrcholů C v G, takže každá hrana v grafu obsahuje alespoň jeden vrchol v C a takhle M a C mají stejnou mohutnost m. Nechat A být množinou prvků S které neodpovídají žádnému vrcholu v C; pak A má alespoň n - m prvky (případně více, pokud C obsahuje vrcholy odpovídající stejnému prvku na obou stranách bipartice) a žádné dva prvky A jsou navzájem srovnatelné. Nechat P být rodinou řetězců vytvořených zahrnutím X a y ve stejném řetězci, kdykoli je hrana (X,y) v M; pak P má n - m řetězy. Proto jsme zkonstruovali antichain a oddíl do řetězců se stejnou mohutností.

Dokázat Kőnigovu větu z Dilworthovy věty pro bipartitní graf G = (U,PROTI,E), tvoří částečný řád na vrcholech G ve kterém u < proti přesně kdy u je v U, proti je v PROTI, a existuje hrana v E z u na proti. Podle Dilworthovy věty existuje antichain A a přepážka do řetězů P oba mají stejnou velikost. Jediné netriviální řetězce v částečném pořadí jsou páry prvků odpovídajících hranám v grafu, takže netriviální řetězce v P tvoří shodu v grafu. Doplněk A tvoří vrcholový kryt G se stejnou mohutností jako tato shoda.

Toto připojení k bipartitní shodě umožňuje vypočítat šířku libovolného částečného pořadí polynomiální čas. Přesněji, n-prvkové dílčí řády šířky k lze rozpoznat včas Ó(kn²) (Felsner, Raghavan a Spinrad 2003 ).

Rozšíření na nekonečné částečně uspořádané množiny

Dilworthova věta pro nekonečné částečně uspořádané množiny uvádí, že částečně uspořádaná množina má konečnou šířku w právě tehdy, pokud je možné jej rozdělit na w řetězy. Předpokládejme, že jde o nekonečný částečný řád P má šířku w, což znamená, že existuje nanejvýš konečné číslo w prvků v jakékoli antichain. Pro jakoukoli podmnožinu S z P, rozklad na w řetězce (pokud existují) lze popsat jako a zbarvení z graf neporovnatelnosti z S (graf, který obsahuje prvky S jako vrcholy, s hranou mezi každým dvěma neporovnatelnými prvky) pomocí w barvy; každá barevná třída ve správném vybarvení grafu nesrovnatelnosti musí být řetěz. Za předpokladu, že P má šířku wa konečnou verzí Dilworthovy věty každá konečná podmnožina S z P má w-barevný graf nesrovnatelnosti. Proto by De Bruijn – Erdősova věta, P sám má také w-barevný graf nesrovnatelnosti, a má tedy požadovaný oddíl do řetězců (Harzheim 2005 ).

Věta se však nerozšiřuje tak jednoduše na částečně uspořádané množiny, ve kterých je šířka, a nejen mohutnost množiny, nekonečná. V takovém případě se může velikost největší antichain a minimální počet řetězců potřebných k pokrytí částečné objednávky od sebe velmi lišit. Zejména pro každé nekonečné hlavní číslo κ existuje nekonečná částečně uspořádaná množina šířky ℵ₀ jehož rozdělení do nejméně řetězců má řetězce κ (Harzheim 2005 ).

Perles (1963) pojednává o analogiích Dilworthovy věty v nekonečném prostředí.

Dvojice Dilworthovy věty (Mirskyho věta)

Dvojník Dilworthovy věty uvádí, že velikost největšího řetězce v částečném pořadí (je-li konečná) se rovná nejmenšímu počtu řetězců, do kterých lze pořadí rozdělit (Mirsky 1971 ). Důkaz toho je mnohem jednodušší než důkaz samotné Dilworthovy věty: pro jakýkoli prvek X, zvažte řetězce, které mají X jako jejich největší prvek, a nechť N(X) označují velikost největší z nich X-maximální řetězy. Pak každá sada N⁻¹(i), skládající se z prvků, které mají stejné hodnoty N, je antichain a tyto antichainy rozdělují částečné pořadí do počtu antichainů, které se rovnají velikosti největšího řetězce.

Dokonalost srovnávacích grafů

A srovnávací graf je neorientovaný graf vytvořený z částečného řádu vytvořením vrcholu na prvek řádu a hranou spojující jakékoli dva srovnatelné prvky. Tak, a klika v grafu srovnatelnosti odpovídá řetězci a nezávislá sada v grafu srovnatelnosti odpovídá antichain. Žádný indukovaný podgraf srovnávacího grafu je sám srovnávací graf, vytvořený z omezení dílčího řádu na podmnožinu jeho prvků.

Neusměrněný graf je perfektní pokud v každém indukovaném podgrafu: chromatické číslo se rovná velikosti největší kliky. Každý srovnatelný graf je dokonalý: jedná se v podstatě pouze o Mirského teorém přepracovaný z hlediska grafu (Berge & Chvátal 1984 ). Podle dokonalá věta o grafu z Lovász (1972), doplněk dokonalého grafu je také perfektní. Proto je doplněk každého grafu srovnatelnosti dokonalý; toto je v podstatě jen samotná Dilworthova věta, přepracovaná v graficko-teoretických podmínkách (Berge & Chvátal 1984 ). Vlastnost komplementace dokonalých grafů tedy může poskytnout alternativní důkaz Dilworthovy věty.

Šířka zvláštních dílčích objednávek

The Booleova mříž B_n je napájecí sada z n- sada prvků X—V zásadě {1, 2, ..., n}-objednáno někým zařazení nebo, notačně, (2^[n], ⊆). Spernerova věta uvádí, že maximální antichain of B_n má velikost maximálně

${ displaystyle operatorname {width} (B_ {n}) = {n vybrat lfloor {n / 2} rfloor}.}$

Jinými slovy, největší rodina nesrovnatelných podmnožin X se získá výběrem podmnožin X které mají střední velikost. The Nerovnost Lubell – Yamamoto – Meshalkin týká se také antichainů v energetické sadě a lze je použít k prokázání Spernerovy věty.

Pokud uspořádáme celá čísla v intervalu [1, 2n] od dělitelnost, podinterval [n + 1, 2n] tvoří antichain s mohutností n. Oddíl tohoto částečného pořadí do n řetězců je snadné dosáhnout: pro každé liché celé číslo m v [1,2n], tvoří řetězec čísel formuláře m2ⁱ. Podle Dilworthovy věty je tedy šířka tohoto částečného řádu n.

The Erdős – Szekeresova věta na monotónních subsekvencích lze interpretovat jako aplikaci Dilworthovy věty na dílčí řády dimenze objednávky dva (Steele 1995 ).

"Konvexní rozměr" antihmota je definován jako minimální počet řetězců potřebných k definování antihmoty a Dilworthova věta může být použita k prokázání, že se rovná šířce přidruženého dílčího řádu; toto spojení vede k polynomiálnímu časovému algoritmu pro konvexní dimenzi (Edelman & Saks 1988 ).

Reference

• Berge, Claude; Chvátal, Václav (1984), Témata o dokonalých grafech, Annals of Discrete Mathematics, 21, Elsevier, s. VII, ISBN  978-0-444-86587-8
• Dilworth, Robert P. (1950), „Decomposition Theorem for Partially Ordered Sets“, Annals of Mathematics, 51 (1): 161–166, doi:10.2307/1969503, JSTOR  1969503.
• Edelman, Paul H .; Saks, Michael E. (1988), „Kombinatorická reprezentace a konvexní rozměr konvexních geometrií“, Objednat, 5 (1): 23–32, doi:10.1007 / BF00143895, S2CID  119826035.
• Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Rozpoznávací algoritmy pro objednávky malé šířky a grafy malého Dilworthova čísla", Objednat, 20 (4): 351–364 (2004), doi:10.1023 / B: ORDE.0000034609.99940.fb, PAN  2079151, S2CID  1363140.
• Fulkerson, D. R. (1956), „Poznámka k Dilworthově teorému o rozkladu pro částečně uspořádané množiny“, Proceedings of the American Mathematical Society, 7 (4): 701–702, doi:10.2307/2033375, JSTOR  2033375.
• Galvin, Fred (1994), „Důkaz Dilworthovy věty o řetězovém rozkladu“, Americký matematický měsíčník, 101 (4): 352–353, doi:10.2307/2975628, JSTOR  2975628, PAN  1270960.
• Greene, Curtis; Kleitman, Daniel J. (1976), „Struktura Spernera ${ displaystyle k}$-families ", J. Combin. Theory Ser. A, 20 (1): 41–68, doi:10.1016/0097-3165(76)90077-7.
• Harzheim, Egbert (2005), Objednané sady Pokroky v matematice (Springer), 7, New York: Springer, Theorem 5.6, str. 60, ISBN  0-387-24219-8, PAN  2127991.
• Lovász, László (1972), „Normální hypergrafy a dokonalá domněnka grafu“, Diskrétní matematika, 2 (3): 253–267, doi:10.1016 / 0012-365X (72) 90006-4.
• Mirsky, Leon (1971), „Duál Dilworthovy věty o rozkladu“, Americký matematický měsíčník, 78 (8): 876–877, doi:10.2307/2316481, JSTOR  2316481.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), „Theorem 3.13“, Sparsity: Graphs, Structures, and AlgorithmsAlgoritmy a kombinatorika, 28, Heidelberg: Springer, str. 42, doi:10.1007/978-3-642-27875-4, hdl:10338.dmlcz / 143192, ISBN  978-3-642-27874-7, PAN  2920058.
• Perles, Micha A. (1963), „K Dilworthově větě v nekonečném případě“, Israel Journal of Mathematics, 1 (2): 108–109, doi:10.1007 / BF02759806, PAN  0168497, S2CID  120943065.
• Steele, J. Michael (1995), "Variace na monotónní podsekvenční téma Erdőse a Szekerese", v Aldous, David; Diaconis, Persi; Spencer, Joel; et al. (eds.), Diskrétní pravděpodobnost a algoritmy (PDF), Svazky IMA v matematice a její aplikace, 72, Springer-Verlag, str. 111–131.

externí odkazy

• Ekvivalence sedmi hlavních vět v kombinatorice
• „Dual of Dilworth's Theorem“, PlanetMath, archivovány z originál dne 2007-07-14
• Babai, László (2005), Přednášky v kombinatorice a pravděpodobnosti, Přednáška 10: Perfektní grafy (PDF), archivovány z originál (PDF) dne 2011-07-20
• Felsner, S .; Raghavan, V. a Spinrad, J. (1999), Algoritmy rozpoznávání pro objednávky malé šířky a grafy malého počtu Dilworth
• Weisstein, Eric W. „Lilma od Dilwortha“. MathWorld.