Dilworthova věta

Dilworthův teorém  je kombinatorický výrok, který charakterizuje extrémní vlastnost posetů : konečný poset lze rozdělit do párových disjunktních řetězců , kde  je počet prvků největšího antiřetězce množiny [1] (také nazývaného šířka posetu) .

Verze věty o nekonečných posetech: Poset má konečnou šířku právě tehdy, když se dá rozdělit na řetězce, ale ne méně.

Dokázal to americký matematik Robert P. Dilworth ( 1914-1993), jehož hlavní oblastí výzkumu byla teorie mříží . 

Důkaz indukcí

Důkaz indukcí o velikosti posetu je založen na Galvinově důkazu [2] .

Dovolit být  konečná částečně uspořádaná množina. Příkaz je triviální, pokud je prázdný. Předpokládejme tedy, že má alespoň jeden prvek a nechť  je maximální prvek .

Podle indukční hypotézy může být pro nějaké celé číslo poset pokrytý disjunktními řetězci a má alespoň jeden antiřetězec o velikosti . Je jasné, že pro . Pro , nechť  je maximální prvek v , který patří do antiřetězce velikosti v a do množiny . Tvrdíme, že  je to antiřetězec. Dovolit být  antichain velikosti obsahující . Opravme libovolné odlišné indexy a . Pak . Nechte _ Pak podle definice . Z toho vyplývá , že od . Pokud si vyměníme role a , dostaneme . To dokazuje, že jde o antiřetězec.

Vraťme se k . Předpokládejme nejprve, že pro některé . Nechť být  řetězem . Pak díky výběru neobsahuje antichain o velikosti . Z indukční hypotézy vyplývá, že je možné pokrýt disjunktními cestami, protože je antiřetězec velikosti v . Podle potřeby je tedy možné krýt řetězy, které se nekříží.

Nyní, jestliže pro každý , pak je antiřetězec velikosti v (protože  je maximum v ). Lze tedy zakrýt řetězy , čímž je důkaz dokončen.

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

Stejně jako jiné výsledky kombinatoriky je Dilworthova věta ekvivalentní Königově větě o párování na bipartitních grafech a některým dalším větám, včetně Hallova svatebního teorému [3] .

Abychom dokázali Dilworthovu větu pro posetu S s n prvky, pomocí Königovy věty definujeme bipartitní graf G = ( U , V , E ) kde U = V = S a ( u , v ) je hrana v G , pokud u < v až S. _ Podle Königovy věty existuje shoda M v G a množina vrcholů C v G tak, že každá hrana z grafu obsahuje alespoň jeden vrchol z C a obě množiny, M a C , mají stejný počet prvků m . Nechť A  je množina prvků S , které neodpovídají žádnému vrcholu v C . Pak má A alespoň n  - m prvků (možná i více, pokud C obsahuje vrcholy odpovídající stejnému prvku na obou stranách bipartitního grafu). Nechť P  je rodina řetězců vytvořená zahrnutím x a y do jednoho řetězce, když je v M hrana ( x , y ) . Pak P má n  - m řetězců. Tím jsme zkonstruovali antiřetězec a rozklad na řetězce se stejným počtem prvků v množině.

Abychom dokázali Königovu větu z Dilworthovy věty pro bipartitní graf G = ( U , V , E ), vytvoříme částečné uspořádání na vrcholech G tak, že u < v přesně nastavíme , když u je obsaženo v U , v je obsaženo ve V a tam je hrana od E od u ve v . Podle Dilworthovy věty existuje antiřetězec A a řetězový rozklad P , obě množiny stejné velikosti. Ale pouze dvojice prvků odpovídajících hranám grafu mohou být netriviálními řetězci v částečném pořadí, takže netriviální řetězce z P tvoří shodu v grafu. Doplněk A tvoří vrcholový kryt G se stejným počtem prvků jako při párování.

Toto spojení s bipartitním párováním umožňuje vypočítat šířku libovolné uspořádané množiny v polynomiálním čase .

Zobecnění na neohraničené částečně uspořádané množiny

Dilworthova věta pro neohraničené částečně uspořádané množiny říká, že taková množina má omezenou šířku w právě tehdy, když ji lze rozložit na w řetězce. Předpokládejme, že nekonečný poset P má šířku w , což znamená, že jakýkoli antiřetězec obsahuje nejvýše konečný počet w prvků. Pro jakoukoli podmnožinu S z P lze rozklad na w řetězce (pokud existuje) popsat jako obarvení grafu nesrovnatelnosti S (grafu, který má prvky S jako vrcholy a hrany pro nesrovnatelné vrcholy) pomocí w barev. Jakákoli třída zbarvení grafu nesrovnatelnosti musí být řetězec. Za předpokladu, že P má šířku w , má podle verze Dilworthovy věty v konečném případě jakákoli konečná podmnožina S z P w -zabarvení grafu nesrovnatelnosti. Podle de Bruijn-Erdősovy věty má tedy P samotné také w -zabarvení grafu nesrovnatelnosti, a to je žádoucí rozdělení do řetězců [4] .

Věta však nelze tak snadno zobecnit na případ posetů, kde šířka není omezena. V tomto případě se velikost maximálního antipramenu a minimálního počtu pramenů potřebných pro pokrytí může výrazně lišit. Konkrétně pro libovolné nekonečné kardinální číslo κ existuje nekonečná částečně uspořádaná množina o šířce ℵ 0 , jejíž rozdělení do řetězců má alespoň κ řetězců [4] .

V roce 1963 [5] bylo pro neohraničený případ získáno prohlášení podobné Dilworthově větě.

Mirského věta

Věta duální k Dilworthově větě, Mirského teorém , tvrdí, že velikost největšího řetězce v částečném řádu (konečný případ) se rovná nejmenšímu počtu antiřetězců, na které lze částečné uspořádání rozložit [6 ] . Důkaz této věty je mnohem jednodušší než důkaz Dilworthovy věty. Pro jakýkoli prvek x vezměte řetězce, které mají x jako svůj maximální prvek, a nechť N ( x ) je velikost největšího z těchto x - maximálních řetězců. Potom každá množina N −1 ( i ) skládající se z prvků, které mají stejné hodnoty N , je antiřetězec a velikost tohoto rozdělení částečně uspořádané množiny na antiřetězce je rovna velikosti největšího řetězce.

Dokonalost grafů srovnatelnosti

Graf srovnatelnosti  je neorientovaný graf vytvořený z částečného řádu vytvořením vrcholů pro každý prvek řádu a hran pro jakékoli dva srovnatelné prvky. Klika v grafu srovnatelnosti tedy odpovídá řetězci a nezávislá množina odpovídá antiřetězci. Jakýkoli vygenerovaný podgraf grafu srovnatelnosti je sám o sobě grafem srovnatelnosti vytvořeným z částečného řádu zúžením na podmnožinu prvků.

Neorientovaný graf je dokonalý , pokud se chromatické číslo v každém vygenerovaném podgrafu rovná velikosti největší kliky. Jakýkoli graf srovnatelnosti je dokonalý – to je jen Mirského teorém, převyprávěný z hlediska teorie grafů [7] . Podle Lovasovy věty o dokonalém grafu [8] je doplněk každého dokonalého grafu také dokonalým grafem. Doplnění jakéhokoli grafu srovnatelnosti je tedy dokonalé. Toto je v podstatě stejný Dilworthův teorém formulovaný z hlediska teorie grafů [7] . Vlastnost komplementarity dokonalých grafů tedy může poskytnout alternativní důkaz Dilworthovy věty.

Šířka speciálních dílčích zakázek

Booleovská mřížka B n  je stupeň množiny X n prvků – řekněme {1, 2, …, n } – uspořádaných inkluzí, nebo formálně (2 [ n ] , ⊆). Spernerův teorém říká, že maximální antiřetězec v B n má velikost nepřesahující

Jinými slovy, největší rodina nesrovnatelných podmnožin množin X se získá výběrem podmnožin X , které mají střední hodnotu. Lubell–Yamamoto–Meshalkinova nerovnost také souvisí s antiřetězci v mocninách množiny a lze ji použít k prokázání Spernerova teorému.

Uspořádáte -li celá čísla v intervalu [1, 2 n ] podle dělitelnosti , podinterval [ n + 1, 2 n ] tvoří antiřetězec velikosti n . Rozklad tohoto dílčího řádu na n řetězců lze snadno získat: pro každé liché m v [1,2 n ] vytvoříme řetězec čísel ve tvaru m 2 i . Podle Dilworthovy věty je tedy šířka tohoto částečného řádu n .

Erdős-Szekeresův teorém o monotónních podsekvencích lze interpretovat jako aplikaci Dilworthova teorému na dílčí řády dimenze dva [9] .

"Konvexní rozměr" antimatroidu je definován jako minimální počet řetězců potřebných k definování antimatroidu a Dilworthův teorém lze použít k prokázání, že se rovná šířce souvisejícího dílčího řádu. Tento vztah vede k časově lineárnímu algoritmu pro nalezení konvexní dimenze [10] .

Poznámky

  1. ↑ Marshall Hall Jr. Kombinatorická teorie. - "MIR", 1970. - S. 90-94. Archivováno 14. října 2011 na Wayback Machine
  2. ↑ Galvin, 1994 .
  3. ↑ Fulkerson, 1956 .
  4. ↑ 12 Harzheim , 2005 .
  5. ↑ Perles, 1963 .
  6. ↑ Mirsky, 1971 .
  7. ↑ 1 2 Berge, Chvátal, 1984 .
  8. ↑ Lovász, 1972 .
  9. ↑ Steele, 1995 .
  10. ↑ Edelman, Saks, 1988 .

Literatura