Teorema lui Dilworth

Teorema lui Dilworth este o afirmație combinatorie care caracterizează o proprietate extremă pentru posete : un poset finit poate fi împărțit în lanțuri disjunse pe perechi , unde este numărul de elemente ale celui mai mare anticlanț al mulțimii [1] (numită și lățimea posetului) . $A$ $n$ $n$ $A$

O versiune a teoremei pentru posete infinite: un poset are lățime finită dacă și numai dacă poate fi descompus în lanțuri, dar nu mai puțin. $w$ $w$

A fost dovedit de matematicianul american Robert P. Dilworth ( 1914-1993), a cărui arie principală de cercetare a fost teoria rețelelor .

Dovada prin inducție

Dovada prin inducție asupra mărimii unui poset se bazează pe demonstrația lui Galvin [2] . $M$

Fie o mulțime finită parțial ordonată. Declarația este banală dacă este goală. Deci, să presupunem că are cel puțin un element și să fie elementul maxim al . $M$ $M$ $M$ $A$ $M$

Prin ipoteza inducției, pentru un număr întreg , un poset poate fi acoperit de lanțuri disjunse și are cel puțin un anticlanț de dimensiune . Este clar că pentru . Pentru , fie elementul maxim în , care aparține anti-lanțului de mărime în și mulțimii . Pretindem că este un antilanț. Fie un antilanț de dimensiune care conține . Să fixăm indici diferiți arbitrari și . Apoi . Lasă . Apoi, prin definiție . Din aceasta rezultă că , din moment ce . Dacă schimbăm rolurile și , obținem . Acest lucru demonstrează că este un antilanț. $k$ $M':=M\setminus \{a\}$ $k$ $C_{1},\puncte, C_{k}$ $A_0$ $k$ $A_{0}\cap C_{i}\neq \emptyset$ $i=1,2,\dots ,k$ $i=1,2,\dots ,k$ $x_{i}$ $C_{i}$ $k$ $M'$ $A:=\{x_{1},x_{2},\dots ,x_{k}\}$ $A$ $A_{i}$ $k$ $x_{i}$ $i$ $j$ $A_{i}\cap C_{j}\neq \emptyset$ $y\în A_{i}\cap C_{j}$ $y\leq x_{j}$ $x_{j}$ $x_{i}\nu \geq x_{j}$ $x_{i}\nu \geq y$ $i$ $j$ $x_{j}\nu \geq x_{i}$ $A$

Să revenim la . Să presupunem mai întâi că pentru unii . Să fie un lanț . Apoi, din cauza alegerii , nu conține un antilanț de dimensiune . Din ipoteza de inducție rezultă că este posibil să se acopere cu căi disjunse, deoarece este un antilanț de dimensiune în . Astfel, este posibilă acoperirea cu lanțuri care nu se intersectează, după caz. $M$ $a\geq x_{i}$ $i\în \{1,2,\puncte ,k\}$ $K$ $\{a\}\cup \{z\in C_{i}:z\leq x_{i}\}$ $x_{i}$ $M\setminus K$ $k$ $M\setminus K$ $k-1$ $A\setminus \{x_{i}\}$ $k-1$ $M\setminus K$ $M$ $k$

Acum, dacă pentru fiecare , atunci este un antilanț de dimensiune în (deoarece este maximul în ). Astfel, poate fi acoperit de lanțuri , ceea ce completează proba. $a\nu \geq x_{i}$ $i\în \{1,2,\puncte ,k\}$ $A\cup\{a\}$ $k+1$ $M$ $A$ $M$ $M$ $k+1$ $\{a\},C_{1},C_{2},\dots ,C_{k}$

Dovada prin teorema lui König

Ca și alte rezultate ale combinatoriei, teorema lui Dilworth este echivalentă cu teorema lui König privind potrivirile pe grafuri bipartite și cu alte teoreme, inclusiv cu teorema nunții lui Hall [3] .

Pentru a demonstra teorema lui Dilworth pentru un poset S cu n elemente, folosind teorema lui König, definim un graf bipartit G = ( U , V , E ) unde U = V = S și ( u , v ) este o muchie în G dacă u < v la S. _ După teorema lui König, există o potrivire M în G și o mulțime de vârfuri C în G , astfel încât fiecare muchie din grafic să conțină cel puțin un vârf din C și ambele mulțimi, M și C , au același număr de elemente m . Fie A mulțimea elementelor lui S care nu corespund niciunui vârf din C . Atunci A are cel puțin n - m elemente (posibil mai multe dacă C conține vârfuri corespunzătoare aceluiași element de pe ambele părți ale graficului bipartit). Fie P familia de lanțuri formată prin includerea x și y într-un lanț atunci când există o margine ( x , y ) în M . Atunci P are n - m lanțuri. Astfel, am construit un antilanț și o descompunere în lanțuri cu același număr de elemente în mulțime.

Pentru a demonstra teorema lui König din teorema lui Dilworth pentru un graf bipartit G = ( U , V , E ) formăm o ordine parțială pe vârfurile lui G stabilind u < v exact când u este conținut în U , v este conținut în V și acolo este o muchie din E din u în v . După teorema lui Dilworth, există un antilanț A și o descompunere a lanțului P , ambele mulțimi de aceeași dimensiune. Dar numai perechile de elemente corespunzătoare marginilor graficului pot fi lanțuri netriviale în ordine parțială, astfel încât lanțurile netriviale din P formează o potrivire în grafic. Complementul A formează o acoperire de vârf G cu același număr de elemente ca și în potrivire.

Această conexiune cu potriviri bipartite permite calcularea lăţimii oricărui set ordonat în timp polinomial .

Generalizare la mulțimi parțial ordonate nemărginite

Teorema lui Dilworth pentru mulțimile parțial ordonate nemărginite afirmă că o astfel de mulțime are lățime mărginită w dacă și numai dacă poate fi descompusă în w lanțuri. Să presupunem că un poset infinit P are lățimea w , ceea ce înseamnă că orice antilanț conține cel mult un număr finit w de elemente. Pentru orice submulțime S a lui P , descompunerea în lanțuri w (dacă există) poate fi descrisă ca o colorare a graficului de incomparabilitate S (un grafic care are elemente ale lui S ca vârfuri și muchii pentru vârfuri incomparabile) folosind w culori. Orice clasă de colorare a unui grafic de incomparabilitate trebuie să fie un lanț. Presupunând că P are lățimea w , după versiunea cu caz finit a teoremei lui Dilworth, orice submulțime finită S a lui P are o colorare w a graficului de incomparabilitate. Astfel, după teorema lui de Bruijn-Erdős , P însuși are și o colorare w a grafului de incomparabilitate, iar aceasta este împărțirea dorită în lanțuri [4] .

Cu toate acestea, teorema nu se generalizează atât de ușor în cazul posetelor în care lățimea nu este mărginită. În acest caz, dimensiunea antișuviței maxime și numărul minim de fire necesare pentru acoperire pot diferi semnificativ. În special, pentru orice număr cardinal infinit κ, există o mulțime infinită parțial ordonată cu lățimea ℵ 0 a cărei împărțire în lanțuri are cel puțin κ lanțuri [4] .

În 1963 [5] , a fost obținută o afirmație similară cu teorema lui Dilworth pentru cazul nemărginit.

Teorema lui Mirsky

Teorema duală cu teorema lui Dilworth, teorema lui Mirsky , afirmă că dimensiunea celui mai mare lanț într-o ordine parțială (cazul final) este egală cu cel mai mic număr de antilanțuri în care poate fi descompusă ordinea parțială [6] ] . Dovada acestei teoreme este mult mai simplă decât cea a teoremei lui Dilworth. Pentru orice element x , luăm lanțuri care au x ca element maxim și fie N ( x ) dimensiunea celui mai mare dintre aceste lanțuri x -maximum . Atunci fiecare mulțime N −1 ( i ) constând din elemente care au aceleași valori ale lui N este un antilanț, iar dimensiunea acestei împărțiri a unui set parțial ordonat în antilanțuri este egală cu dimensiunea celui mai mare lanț.

Perfecțiunea graficelor de comparabilitate

Un grafic de comparabilitate este un grafic nedirecționat format dintr-o ordine parțială prin crearea de vârfuri pentru fiecare element al ordinii și muchii pentru oricare două elemente comparabile. Astfel, o clică din graficul de comparabilitate corespunde unui lanț, iar o mulțime independentă corespunde unui antilanț. Orice subgraf generat al unui grafic de comparabilitate este el însuși un grafic de comparabilitate format dintr-o ordine parțială prin restrângerea la un subset de elemente.

Un grafic nedirecționat este perfect dacă numărul cromatic din fiecare subgraf generat este egal cu dimensiunea celei mai mari clicuri. Orice grafic de comparabilitate este perfect - aceasta este doar teorema lui Mirsky, repovestită în termeni de teoria grafurilor [7] . După teorema grafului perfect a lui Lovas [8] , complementul oricărui graf perfect este, de asemenea, un graf perfect. Astfel, complementul oricărui grafic de comparabilitate este perfect. Aceasta este în esență aceeași teoremă a lui Dilworth formulată în termenii teoriei grafurilor [7] . Astfel, proprietatea de complementaritate a graficelor perfecte poate oferi o demonstrație alternativă a teoremei lui Dilworth.

Lățimea comenzilor parțiale speciale

Rețeaua booleană B n este gradul unei mulțimi X de n elemente — să zicem, {1, 2, …, n } — ordonate prin includere sau, formal, (2 [ n ] , ⊆). Teorema lui Sperner afirmă că antilanțul maxim din B n are o dimensiune care nu depășește

{\mbox{lățime}}(B_{n})={n \alegeți \lfloor {n/2}\rfloor }.

Cu alte cuvinte, cea mai mare familie de submulțimi de incomparabilitate ale mulțimilor X se obține prin alegerea unor submulțimi de X care au o medie. Inegalitatea Lubell–Yamamoto–Meshalkin este, de asemenea, legată de antilanțuri în puterile unei mulțimi și poate fi folosită pentru a demonstra teorema lui Sperner.

Dacă ordonați numerele întregi din intervalul [1, 2 n ] după divizibilitate , subintervalul [ n + 1, 2 n ] formează un anticlanț de dimensiune n . Descompunerea acestei ordine parțiale în n lanțuri este ușor de obținut: pentru fiecare m impar din [1,2 n ], formăm un lanț de numere de forma m 2 i . Astfel, după teorema lui Dilworth, lățimea acestui ordin parțial este n .

Teorema Erdős-Szekeres asupra subsecvențelor monotone poate fi interpretată ca o aplicare a teoremei Dilworth la ordinele parțiale de dimensiune doi [9] .

„Dimensiunea convexă” a unui antimatroid este definită ca numărul minim de lanțuri necesare pentru a defini un antimatroid, iar teorema lui Dilworth poate fi folosită pentru a arăta că este egală cu lățimea ordinului parțial asociat. Această relație conduce la un algoritm liniar în timp pentru găsirea unei dimensiuni convexe [10] .

Note

↑ Marshall Hall Jr. Teoria combinatorie . - „MIR”, 1970. - S. 90-94. Arhivat pe 14 octombrie 2011 la Wayback Machine
↑ Galvin, 1994 .
↑ Fulkerson, 1956 .
↑ 12 Harzheim , 2005 .
↑ Perles, 1963 .
↑ Mirsky, 1971 .
↑ 1 2 Berge, Chvatal, 1984 .
↑ Lovász, 1972 .
↑ Steele, 1995 .
↑ Edelman, Saks, 1988 .

Literatură

Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparitate: grafice, structuri și algoritmi. - Heidelberg: Springer, 2012. - T. 28. - P. 42. - (Algoritmi și combinatorică). — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .
Egbert Harzheim. seturi comandate. - New York: Springer, 2005. - V. 7. - S. Teorema 5.6, p.60. - (Avansuri în matematică (Springer)). - ISBN 0-387-24219-8 .
Claude Berge, Václav Chvatal. Subiecte despre graficele perfecte. - Elsevier, 1984. - T. 21 . - C. viii . — ISBN 9780444865878 .
Robert P. Dilworth. O teoremă de descompunere pentru mulțimi parțial ordonate // Analele matematicii . - 1950. - T. 51 , nr. 1 . - S. 161-166 . - doi : 10.2307/1969503 .
Paul H. Edelman, Michael E. Saks. Reprezentarea combinatorie si dimensiunea convexa a geometriilor convexe // Ordinea . - 1988. - V. 5 , nr. 1 . - S. 23-32 . - doi : 10.1007/BF00143895 .
D. R. Fulkerson. Notă despre teorema de descompunere a lui Dilworth pentru mulțimi parțial ordonate // Proceedings of the American Mathematical Society . - 1956. - Vol. 7 , iss. 4 . - P. 701-702 .
Fred Galvin. O dovadă a teoremei de descompunere în lanț a lui Dilworth // The American Mathematical Monthly . - 1994. - T. 101 , nr. 4 . - S. 352-353 . - doi : 10.2307/2975628 .
Laszlo Lovasz. Hipergrafele normale și conjectura grafică perfectă // Matematică discretă . - 1972. - T. 2 . - S. 253-267 . - doi : 10.1016/0012-365X(72)90006-4 .
Leon Mirsky. O duală a teoremei de descompunere a lui Dilworth // American Mathematical Monthly . - 1971. - T. 78 , nr. 8 . - S. 876-877 . - doi : 10.2307/2316481 . .
Micha A. Perles. Despre teorema lui Dilworth în cazul infinit // Israel Journal of Mathematics. - 1963. - T. 1 . - S. 108-109 . - doi : 10.1007/BF02759806 .
J. Michael Steele. Probabilitate discretă și algoritmi / David Aldous, Persi Diaconis, Joel Spencer, J. Michael Steele. - Springer-Verlag, 1995. - T. 72. - S. 111-131. - (Volume IMA în matematică și aplicațiile sale).
A. V. Spivak, Lanțuri și antilanțuri , Centrul de Educație Matematică Continuă din Moscova , materiale ale școlii de matematică vizitatoare, 7-11.04.2004.]
Echivalența a șapte teoreme majore în combinatorică
Teorema duală a lui Dilworth (link indisponibil) . PlanetMath . Consultat la 12 iunie 2011. Arhivat din original pe 14 iulie 2007. (nedefinit)
Babai, Laszlo. Note de curs în Combinatorică și probabilitate, Curs 10: Perfect Graphs (2005). Preluat la 12 iunie 2011. Arhivat din original la 14 mai 2012. (nedefinit)
Felsner, S., Raghavan, V. și Spinrad, J. Algoritmi de recunoaștere pentru ordinele de lățime mică și grafice ale numărului mic Dilworth (1999). Preluat la 12 iunie 2011. Arhivat din original la 14 mai 2012. (nedefinit)
Weisstein, Eric W. Dilworth's Lema (engleză) pe site-ul Wolfram MathWorld .