Twierdzenie Dilworth w zamówieniu teorię i kombinatorycznych Ze względu na Robert Dilworth , charakteryzuje szerokość któregokolwiek (częściowe) zakończone w kategoriach partycji tego celu w minimalnej liczby kanałów .
W uporządkowanym zestawie antychain to część, której elementy są dwa na dwa nieporównywalne, a łańcuch to część, której elementy są dwa na dwa porównywalne. Twierdzenie Dilwortha ustanawia, dla skończonego porządku , istnienie antychain A i podział uporządkowanego zbioru na rodzinę P łańcuchów, tak że A i P mają taką samą liczność . Dla takich A i P , A jest koniecznie antychainem maksimum kardynalskiego (ponieważ każdy antychain ma co najwyżej jeden element w każdym elemencie P ), a P jest koniecznie podziałem w łańcuchach minimum kardynalnego (ponieważ każda partycja w łańcuchach ma co najmniej jeden ciąg na element A ). Szerokość rzędu częściowego (tj. Maksymalny rozmiar antychaina) można zatem przedefiniować jako wspólny kardynał A i P lub jako minimalny rozmiar podziału w łańcuchach.
Uogólnienie twierdzenie stanów to rozkaz (niekoniecznie skończonych) ma skończoną szerokość W , wtedy i tylko wtedy może być podzielona w sieci, ale nie mniej.
Poniższy dowód, poprzez indukcję rozmiaru częściowo uporządkowanego zbioru S , jest inspirowany dowodem Galvina (en) .
Wynik jest natychmiastowy, jeśli S jest pusty. Załóżmy, że S nie jest puste, niech a będzie jednym z jego maksymalnych elementów i zastosuj hipotezę indukcji do uporządkowanego zbioru T = S \ { a } . Dla pewnej liczby całkowitej k istnieje podział T na k łańcuchów C 1 ,…, C k i antychain A 0 z T kardynała k . Dla każdego i od 1 do k istnieją w C i elementy należące do co najmniej jednego antychaina T o rozmiarze k (na przykład: elementy wspólne dla C i i A 0 ); niech x i być Największą z nich i A í taki powiązany antyłańcuch. Zatem zbiór A = { x 1 ,…, x k } jest antychainem. Rzeczywiście, dla wszystkich odrębnych indeksów i i j istnieje co najmniej jeden y wspólny dla A i i C j , a taki element spełnia y ≤ x j (z definicji x j ), więc x i ≱ x j (ponieważ x ja ≱ y ).
Wróćmy do S i rozróżnijmy dwa przypadki.
Podobnie jak wiele innych kombinatorycznych wyniki, łącznie z małżeństw lemat o Hall , Dilworth twierdzenie jest równoważne Konig twierdzenia na temat sprzęgieł o graf dwudzielny .
Aby wywnioskować z twierdzenia Kőniga twierdzenia Dilwortha, dla częściowo uporządkowanego zbioru S z n elementami, definiujemy dwudzielny graf G = ( U , V , E ) przez: U = V = S i element u z U jest połączony z elementem V o V o krawędzi G gdy u <V w S . Zgodnie z twierdzeniem Kőniga, w G istnieje sprzężenie M i poprzeczne C tego samego kardynalnego m . Niech A będzie zbiorem elementów S, które nie odpowiadają żadnemu wierzchołkowi C ; wtedy A ma co najmniej n - m elementów (prawdopodobnie więcej, jeśli C zawiera wierzchołki w U i V odpowiadające temu samemu elementowi S ). Z definicji poprzeczki każda krawędź ma koniec w C , a zatem A jest antychainem. Niech P będzie rodziną łańcuchów utworzoną przez umieszczenie x i y w tym samym łańcuchu za każdym razem, gdy są one połączone krawędzią M ; następnie P a n - m struny. Dlatego skonstruowaliśmy antychain i przegrodę w łańcuchach tego samego kardynała.
I odwrotnie, aby wydedukować twierdzenie Kőniga z twierdzenia Dilwortha, dla grafu dwudzielnego G = ( U , V , E ), uporządkujemy wierzchołki G przez ustawienie: u <v wtedy i tylko wtedy, gdy u jest w U , v w V i krawędź E. łączy je. Zgodnie z twierdzeniem Dilwortha istnieje antychain A i podział na łańcuchy P o tej samej wielkości. Ale jedynymi nietrywialnymi łańcuchami są tutaj pary elementów odpowiadające krawędziom wykresu, więc nietrywialne łańcuchy P tworzą sprzężenie. Dopełnienie A tworzy poprzeczkę z taką samą licznością jak to sprzężenie.
To powiązanie z dwudzielnymi sprzężeniami grafowymi umożliwia obliczenie szerokości dowolnego skończonego rzędu cząstkowego w czasie wielomianowym .
Na nieskończenie zestaw T , rozkaz jest nadal o szerokości mniejszej niż lub równa całkowitej wagowych (w przypadku a) tylko wtedy, gdy T jest związkiem w łańcuchach rozłącznych.
Rzeczywiście uporządkowany zbiór S jest związkiem w łańcuchach rozłącznych, wtedy i tylko wtedy, gdy istnieje zabarwienia przez w kolorach wykresie nieporównywalne z S (z nieukierunkowane wykres , którego wierzchołki są elementy S i krawędzie łączenia pary elementów nieporównywalne). W konsekwencji, jeśli szerokość rzędu na T jest mniejsza lub równa w , to dla dowolnej części skończonej S z T (o szerokości a fortiori powiększonej o w ) istnieje, zgodnie ze skończoną wersją twierdzenia Dilwortha, barwienie w kolory niedopasowanie wykres S . Według do De Bruijn-Erdős twierdzenia , wykres nieporównywalności T jest wtedy również „ w -colorable”, więc T jest sumą wag łańcuchów rozłącznych.
Jednak twierdzenie nie rozciąga się na rzędy o nieskończonej szerokości: dla każdego nieskończonego kardynala κ istnieje porządek, w którym każdy antychain jest skończony, ale którego wszystkie przegrody w łańcuchach mają wielkość co najmniej κ.
Micha Perles bada analogi twierdzenia Dilwortha w przypadku nieskończonym.
Twierdzenie Mirsky'ego (in) , podwójne twierdzenie Dilwortha, ustala, że porządek częściowy, maksymalny rozmiar łańcuchów, jeśli się skończy, jest równy mniejszemu rozmiarowi podziału w antychainach. Dowód jest znacznie prostszy: dla dowolnego elementu x niech N ( x ) będzie maksymalnym rozmiarem łańcuchów, z których x jest największym elementem, wtedy N –1 ({ i }) tworzy podział na n łańcuchów, jeśli n to maksymalny rozmiar ciągów.
Wykres porównywalność uporządkowanego zestawu jest nieukierunkowane wykres, którego wierzchołki są elementy zestawu, i krawędzie połączenia pary podobnych elementów. Kliknięcie na wykresie odpowiada zatem w łańcuchu, i stabilny An antyłańcuch. Każdy podgraf indukowany z wykresu porównywalności jest sam w sobie grafem porównawczym: tym o kolejności ograniczonej do jego wierzchołków.
Graf nieukierunkowany jest doskonały, jeśli w jakimkolwiek podgrafie indukowanym liczba chromatyczna jest równa wielkości największej kliki. Każdy wykres porównywalności jest doskonały: jest to zasadniczo twierdzenie Mirsky'ego, przeformułowane w kategoriach teorii grafów . Zgodnie z twierdzeniem o wykresie doskonałym Lovásza , dopełnienie dowolnego wykresu doskonałego jest również doskonałe. Dlatego uzupełnienie dowolnego wykresu porównywalności jest doskonałe; jest to przeformułowanie twierdzenia Dilwortha w kategoriach teorii grafów, co dostarcza innego dowodu.