Dilvort teoremasi - Dilworths theorem

Yilda matematika, hududlarida tartib nazariyasi va kombinatorika, Dilvort teoremasi xarakterlaydi kengligi har qanday cheklangan qisman buyurtma qilingan to'plam a nuqtai nazaridan bo'lim buyurtmaning minimal soniga zanjirlar. U matematik uchun nomlangan Robert P. Dilvort  (1950 ).

An antichain qisman tartiblangan to'plamda ikkitasi bir-biriga taqqoslanmaydigan elementlar to'plami, zanjir esa har ikkalasi taqqoslanadigan elementlar to'plamidir. Zanjir dekompozitsiyasi - bu buyurtma elementlarining bo'linishi ajratish zanjirlar. Dilvort teoremasi shuni ko'rsatadiki, har qanday cheklangan qisman tartiblangan to'plamda eng katta antichain eng kichik zanjirning parchalanishi bilan bir xil darajada bo'ladi. Bu erda antichainning kattaligi uning elementlari sonidir va zanjirning parchalanish hajmi uning zanjirlari sonidir. Qisman tartibning kengligi antichain va zanjirning parchalanishining umumiy hajmi sifatida aniqlanadi.

Teoremaning cheksiz qisman tartiblangan to'plamlari versiyasida, ko'p sonli zanjirlarga parchalanish mavjud bo'lganda yoki antichain o'lchamiga cheklangan yuqori chegara mavjud bo'lganda, eng katta antichain va eng kichik zanjir dekompozitsiyasining o'lchamlari ko'rsatilgan. yana teng.

Induktiv isbot

Qisman buyurtma qilingan to'plam hajmiga induksiya bo'yicha quyidagi dalil ${ displaystyle P}$ ga asoslangan Galvin  (1994 ).

Ruxsat bering ${ displaystyle P}$ cheklangan qisman buyurtma qilingan to'plam bo'lishi. Teorema, agar ahamiyatsiz bo'lsa ${ displaystyle P}$ bo'sh Shunday qilib, taxmin qiling ${ displaystyle P}$ kamida bitta elementga ega va ruxsat bering ${ displaystyle a}$ ning maksimal elementi bo'lishi ${ displaystyle P}$.

Induksiya bo'yicha biz biron bir butun son uchun buni qabul qilamiz ${ displaystyle k}$ qisman buyurtma qilingan to'plam ${ displaystyle P ': = P setminus {a }}$ tomonidan qoplanishi mumkin ${ displaystyle k}$ ajratilgan zanjirlar ${ displaystyle C_ {1}, dots, C_ {k}}$ va kamida bitta antichainga ega ${ displaystyle A_ {0}}$ hajmi ${ displaystyle k}$. Shubhasiz, ${ displaystyle A_ {0} cap C_ {i} neq emptyset}$ uchun ${ displaystyle i = 1,2, nuqta, k}$. Uchun ${ displaystyle i = 1,2, nuqta, k}$, ruxsat bering ${ displaystyle x_ {i}}$ ichida maksimal element bo'ling ${ displaystyle C_ {i}}$ bu antichain o'lchamiga tegishli ${ displaystyle k}$ yilda ${ displaystyle P '}$va sozlang ${ displaystyle A: = {x_ {1}, x_ {2}, nuqtalar, x_ {k} }}$. Biz buni da'vo qilamiz ${ displaystyle A}$ antichain. Ruxsat bering ${ displaystyle A_ {i}}$ o'lchamdagi antichain bo'ling ${ displaystyle k}$ o'z ichiga oladi ${ displaystyle x_ {i}}$. O'zboshimchalik bilan aniq indekslarni tuzatish ${ displaystyle i}$ va ${ displaystyle j}$. Keyin ${ displaystyle A_ {i} cap C_ {j} neq emptyset}$. Ruxsat bering ${ displaystyle y A_ {i} cap C_ {j}} da$. Keyin ${ displaystyle y leq x_ {j}}$, ning ta'rifi bilan ${ displaystyle x_ {j}}$. Bu shuni anglatadiki ${ displaystyle x_ {i} not geq x_ {j}}$, beri ${ displaystyle x_ {i} not geq y}$. Rollarini almashtirib ${ displaystyle i}$ va ${ displaystyle j}$ ushbu bahsda biz ham bor ${ displaystyle x_ {j} not geq x_ {i}}$. Bu buni tasdiqlaydi ${ displaystyle A}$ antichain.

Biz endi qaytamiz ${ displaystyle P}$. Avval buni aytaylik ${ displaystyle a geq x_ {i}}$ kimdir uchun ${ displaystyle i in {1,2, dots, k }}$. Ruxsat bering ${ displaystyle K}$ zanjir bo'ling $C {i} da { displaystyle {a } cup {z : z leq x_ {i} }}$. Keyin tanlov bilan ${ displaystyle x_ {i}}$, ${ displaystyle P setminus K}$ antichain o'lchamiga ega emas ${ displaystyle k}$. Keyin induksiya shuni nazarda tutadi ${ displaystyle P setminus K}$ tomonidan qoplanishi mumkin ${ displaystyle k-1}$ beri zanjirlar ${ displaystyle A setminus {x_ {i} }}$ kattalikka qarshi zanjir ${ displaystyle k-1}$ yilda ${ displaystyle P setminus K}$. Shunday qilib, ${ displaystyle P}$ tomonidan qoplanishi mumkin ${ displaystyle k}$ kerak bo'lganda, ajratilgan zanjirlar. Keyingi, agar ${ displaystyle a not geq x_ {i}}$ har biriga ${ displaystyle i in {1,2, dots, k }}$, keyin ${ displaystyle A cup {a }}$ kattalikka qarshi zanjir ${ displaystyle k + 1}$ yilda ${ displaystyle P}$ (beri ${ displaystyle a}$ maksimal ${ displaystyle P}$). Endi ${ displaystyle P}$ bilan qoplanishi mumkin ${ displaystyle k + 1}$ zanjirlar ${ displaystyle {a }, C_ {1}, C_ {2}, nuqtalar, C_ {k}}$, dalilni to'ldirish.

Kunig teoremasi orqali isbot

Dilvort teoremasini Knig teoremasi orqali isbotlash: bipartitli grafikni qisman tartibdan tuzish va zanjirlarga mos keladigan tarzda ajratish

Kombinatorikadagi bir qator boshqa natijalar singari, Dilvort teoremasi ham tengdir Kenig teoremasi kuni ikki tomonlama grafik taalukli va boshqa bir qator teoremalar, shu jumladan Xollning nikoh teoremasi (Fulkerson 1956 yil ).

Qisman tartib uchun Dilvort teoremasini isbotlash S bilan n elementlar, Kőnig teoremasidan foydalanib, ikki tomonlama grafikani aniqlaydi G = (U,V,E) qayerda U = V = S va qaerda (siz,v) ning chekkasi G qachon siz < v yilda S. Kunig teoremasi bo'yicha, mos keladigan narsa mavjud M yilda Gva tepaliklar to'plami C yilda G, grafadagi har bir chekkada kamida bitta vertikal bo'lishi kerak C va shunday M va C bir xil kardinallikka ega m. Ruxsat bering A ning elementlari to'plami bo'lishi S ning har qanday tepasiga to'g'ri kelmaydigan C; keyin A kamida bor n - m elementlar (ehtimol ko'proq bo'lsa) C ikkala qismning ikkala tomonida bir xil elementga mos keladigan tepaliklarni o'z ichiga oladi) va ning ikkala elementi yo'q A bir-biri bilan taqqoslash mumkin. Ruxsat bering P qo'shish orqali hosil qilingan zanjirlar oilasi bo'ling x va y har qanday chekka bo'lganda bir xil zanjirda (x,y) ichida M; keyin P bor n - m zanjirlar. Shuning uchun biz antichain va bir xil kuchga ega zanjirlarga bo'linma yaratdik.

Ikki tomonlama grafika uchun Dilvort teoremasidan König teoremasini isbotlash G = (U,V,E) ning tepalarida qisman tartib hosil qiling G unda siz < v aynan qachon siz ichida U, v ichida Vva chekka mavjud E dan siz ga v. Dilvort teoremasi bo'yicha antichain mavjud A va zanjirlarga bo'linish P ikkalasi ham bir xil o'lchamga ega. Ammo qisman tartibdagi yagona noan'anaviy zanjirlar grafadagi qirralarga mos keladigan juft elementlardir, shuning uchun nrivrivial zanjirlar P grafada mos keladigan shaklni hosil qiling. Ning to'ldiruvchisi A ichida tepalik qopqog'ini hosil qiladi G ushbu mos keladigan kardinallik bilan.

Ikki tomonlama moslik bilan ushbu ulanish har qanday qisman buyurtmaning kengligini hisoblashga imkon beradi polinom vaqti. Aniqrog'i, n- elementning kengligi qisman buyurtmalari k vaqtida tan olinishi mumkin O(kn²) (Felsner, Raghavan va Spinrad 2003 yil ).

Cheksiz qisman tartiblangan to'plamlarga kengaytma

Dilvort teoremasida cheksiz qisman tartiblangan to'plamlar uchun qisman tartiblangan to'plamning cheklangan kengligi borligi aytilgan w va agar u qismlarga bo'linishi mumkin bo'lsa w zanjirlar. Faraz qilaylik, cheksiz qisman tartib P kengligi bor w, eng ko'p sonli son borligini anglatadi w har qanday antichain tarkibidagi elementlarning. Har qanday kichik to'plam uchun S ning P, parchalanish w zanjirlar (agar mavjud bo'lsa) a sifatida tavsiflanishi mumkin rang berish ning taqqoslanmaslik grafigi ning S (ning elementlariga ega bo'lgan grafik S tepaliklar sifatida, har ikkala tengsiz elementlar orasidagi chekka bilan) w ranglar; taqqoslanmaslik grafigining to'g'ri ranglanishidagi har bir rang sinfi zanjir bo'lishi kerak. Bu taxmin bilan P kengligi bor wva Dilvort teoremasining cheklangan versiyasiga ko'ra har bir cheklangan kichik to'plam S ning P bor w- rang-barang taqqoslanmaslik grafigi. Shuning uchun, tomonidan De Bryuyn-Erdes teoremasi, P o'zi ham bor w- rang-barang taqqoslanmaslik grafigi va shu bilan kerakli bo'lakni zanjirlarga ajratish (Xartsgeym 2005 yil ).

Biroq, teorema shunchaki shunchaki kenglikning emas, balki kenglikning cheksizligi bo'lgan qisman tartiblangan to'plamlarga tarqalmaydi. Bu holda eng katta antichainning hajmi va qisman tartibni qoplash uchun zarur bo'lgan minimal zanjirlar bir-biridan juda farq qilishi mumkin. Xususan, har bir cheksiz kardinal son uchun cheksiz qisman tartiblangan kenglik to'plami mavjud ℵ₀ eng kichik zanjirlarga bo'linish κ zanjirga ega (Xartsgeym 2005 yil ).

Perles (1963) cheksiz sharoitda Dilvort teoremasining analoglarini muhokama qiladi.

Dilvort teoremasining duali (Mirskiy teoremasi)

Dilvort teoremasining ikkitasi shuni ko'rsatadiki, eng katta zanjirning hajmi qisman tartibda (agar cheklangan bo'lsa) buyurtma bo'linishi mumkin bo'lgan eng kichik antichainlarga teng (Mirskiy 1971 yil ). Buning isboti Dilvort teoremasining o'zi isbotiga qaraganda ancha sodda: har qanday element uchun x, mavjud bo'lgan zanjirlarni ko'rib chiqing x ularning eng katta elementi sifatida va ruxsat bering N(x) bularning eng kattasining hajmini belgilang x- maksimal zanjirlar. Keyin har bir to'plam N⁻¹(men) ning teng qiymatlariga ega bo'lgan elementlardan iborat N, antichain va bu antichainlar qisman tartibni eng katta zanjirning kattaligiga teng bo'lgan bir qator antichainlarga ajratadi.

Taqqoslash grafikalarining mukammalligi

A taqqoslash grafigi bu yo'naltirilmagan grafik tartibning bir elementi uchun tepalik va har qanday taqqoslanadigan ikkita elementni bog'laydigan chekka yaratish orqali qisman tartibdan hosil bo'lgan. Shunday qilib, a klik taqqoslanadigan grafikada zanjirga to'g'ri keladi va an mustaqil to'plam taqqoslash grafigida antichainga to'g'ri keladi. Har qanday induktsiya qilingan subgraf taqqoslash grafigining o'zi bu qisman tartibni uning elementlari to'plamiga cheklashidan hosil bo'lgan taqqoslash grafigi.

Yo'naltirilmagan grafik mukammal agar har bir indüklenen subgrafada xromatik raqam eng katta klik o'lchamiga teng. Har qanday taqqoslash grafigi mukammaldir: bu asosan Mirskiy teoremasi bo'lib, u grafik-nazariy jihatdan takrorlangan (Berge va Chvatal 1984 yil ). Tomonidan mukammal grafik teoremasi ning Lovash (1972), to'ldiruvchi har qanday mukammal grafika ham mukammaldir. Shuning uchun har qanday taqqoslash grafigini to'ldiruvchisi mukammaldir; bu asosan Dilvort teoremasining o'zi, grafik-nazariy jihatdan qayta yozilgan (Berge va Chvatal 1984 yil ). Shunday qilib, mukammal grafikalarning komplementatsiya xususiyati Dilvort teoremasining muqobil isboti bo'lishi mumkin.

Maxsus qisman buyurtmalarning kengligi

The Mantiq panjarasi B_n bo'ladi quvvat o'rnatilgan ning n- elementlar to'plami X- asosan {1, 2,…, n} - tomonidan tartibga solingan qo'shilish yoki notatsional ravishda (2^[n], ⊆). Sperner teoremasi ning maksimal antichainini bildiradi B_n eng katta hajmga ega

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

Boshqacha qilib aytganda, tengsiz kichik guruhlarning eng katta oilasi X ning pastki to'plamlarini tanlash orqali olinadi X o'rtacha kattalikka ega. The Lyubell-Yamamoto-Meshalkin tengsizligi shuningdek, quvvat to'plamidagi antichainlarga taalluqlidir va Sperner teoremasini isbotlash uchun ishlatilishi mumkin.

Agar biz butun sonlarni [1, 2 oralig'ida buyurtma qilsakn] tomonidan bo'linish, subinterval [n + 1, 2n] kardinalligi bilan antichain hosil qiladi n. Ushbu qisman buyurtmaning bir qismi n zanjirlarga erishish oson: har bir g'alati tamsayı uchun m yilda [1,2n], shakl raqamlari zanjirini hosil qiling m2^men. Shuning uchun, Dilvort teoremasiga ko'ra, bu qisman tartibning kengligi n.

The Erduss-Sekeres teoremasi monoton ketma-ketliklar bo'yicha Dilvort teoremasining qisman buyruqlarga qo'llanilishi sifatida talqin qilinishi mumkin buyurtma hajmi ikki (Stil 1995 yil ).

An "ning konveks o'lchovi" antimatroid antimatroidni aniqlash uchun zarur bo'lgan minimal zanjirlar soni sifatida aniqlanadi va Dilvort teoremasi bilan bog'liq qismli tartibning kengligiga teng ekanligini ko'rsatish uchun foydalanish mumkin; bu ulanish konveks o'lchovi uchun polinom vaqt algoritmiga olib keladi (Edelman va Saks 1988 yil ).

Adabiyotlar

• Berge, Klod; Chvatal, Vatslav (1984), Mukammal grafikalar bo'yicha mavzular, Diskret matematika yilnomalari, 21, Elsevier, p. viii, ISBN  978-0-444-86587-8
• Dilvort, Robert P. (1950), "Qisman tartiblangan to'plamlar uchun dekompozitsiya teoremasi", Matematika yilnomalari, 51 (1): 161–166, doi:10.2307/1969503, JSTOR  1969503.
• Edelman, Pol X.; Saks, Maykl E. (1988), "Kombinatoriya tasviri va konveks geometriyasining konveks o'lchovi", Buyurtma, 5 (1): 23–32, doi:10.1007 / BF00143895, S2CID  119826035.
• Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremi (2003), "Kichik kenglikdagi buyruqlarni va kichik Diluort raqamining grafikalarini tanib olish algoritmlari", Buyurtma, 20 (4): 351–364 (2004), doi:10.1023 / B: ORDE.0000034609.99940.fb, JANOB  2079151, S2CID  1363140.
• Fulkerson, D. R. (1956), "Dilvortning qisman tartiblangan to'plamlar uchun parchalanish teoremasi to'g'risida eslatma", Amerika matematik jamiyati materiallari, 7 (4): 701–702, doi:10.2307/2033375, JSTOR  2033375.
• Galvin, Fred (1994), "Dilvort zanjirining parchalanish teoremasining isboti", Amerika matematikasi oyligi, 101 (4): 352–353, doi:10.2307/2975628, JSTOR  2975628, JANOB  1270960.
• Grin, Kertis; Kleitman, Daniel J. (1976), "Spernerning tuzilishi ${ displaystyle k}$- oilalar ", J. Kombin. Nazariya ser. A, 20 (1): 41–68, doi:10.1016/0097-3165(76)90077-7.
• Xartsgeym, Egbert (2005), Buyurtma qilingan to'plamlar, Matematikadagi yutuqlar (Springer), 7, Nyu-York: Springer, Teorema 5.6, p. 60, ISBN  0-387-24219-8, JANOB  2127991.
• Lovash, Laslo (1972), "Oddiy gipergrafalar va mukammal grafik gipotezasi", Diskret matematika, 2 (3): 253–267, doi:10.1016 / 0012-365X (72) 90006-4.
• Mirskiy, Leon (1971), "Dilvortning parchalanish teoremasi duali", Amerika matematik oyligi, 78 (8): 876–877, doi:10.2307/2316481, JSTOR  2316481.
• Neshetil, Jaroslav; Ossona de Mendez, Patris (2012), "Teorema 3.13", Sariqlik: Grafika, tuzilmalar va algoritmlar, Algoritmlar va kombinatorika, 28, Heidelberg: Springer, p. 42, doi:10.1007/978-3-642-27875-4, hdl:10338.dmlcz / 143192, ISBN  978-3-642-27874-7, JANOB  2920058.
• Perles, Micha A. (1963), "Cheksiz holatda Dilvort teoremasi to'g'risida", Isroil matematika jurnali, 1 (2): 108–109, doi:10.1007 / BF02759806, JANOB  0168497, S2CID  120943065.
• Stil, J. Maykl (1995), "Erdo'z va Sekeresning monoton keyingi mavzusidagi farqlar", Aldous, Devid; Diakonis, forscha; Spenser, Joel; va boshq. (tahr.), Diskret ehtimolliklar va algoritmlar (PDF), Matematika bo'yicha IMA jildlari va uning qo'llanilishi, 72, Springer-Verlag, bet 111-131.

Tashqi havolalar

• Kombinatorikadagi yettita asosiy teoremalarning ekvivalenti
• "Dilvort teoremasi duali", PlanetMath, dan arxivlangan asl nusxasi 2007-07-14
• Babay, Laslo (2005), Kombinatorika va ehtimollik bo'yicha ma'ruza matnlari, 10-ma'ruza: mukammal grafikalar (PDF), dan arxivlangan asl nusxasi (PDF) 2011-07-20
• Felsner, S .; Raghavan, V. & Spinrad, J. (1999), Kichik kenglik buyurtmalarini tanib olish algoritmlari va kichik Dilvort sonining grafikalari
• Vayshteyn, Erik V. "Dilvortning limmasi". MathWorld.