Кіріспе
Математикада, тәртіп теориясы және комбинаторика салаларында Дилворт теоремасы кез келген шекті ішінара реттелген жиынның енін, тәртіптің ең аз тізбектерге бөлінуі арқылы сипаттайды. Ол математик үшін аталған. Ішінара реттелген жиынтықтағы антижелі – бір-бірімен салыстырылмасатын элементтер жиыны, ал тізбек – кез келген екі элементі салыстырылатын элементтер жиыны. Тізбектерге жіктеу – тәртіп элементтерінің өзара байланыссыз тізбектерге бөлінуі. Дилворт теоремасы бойынша, кез келген шекті ішінара реттелген жиынның ең үлкен антижелісінің мөлшері ең кішкентай тізбектерге жіктеудің мөлшерімен бірдей болады. Мұнда антижелінің мөлшері – оның элементтерінің саны, ал тізбектерге жіктеудің мөлшері – тізбектердің саны. Ішінара тәртіптің ені антижелінің және тізбектерге жіктеудің ортақ мөлшері ретінде анықталады. Шексіз ішінара реттелген жиынтар үшін теореманың нұсқасы, егер шексіз көптеген тізбектерге жіктеу болса немесе антижелінің мөлшеріне шекті жоғарғы шек болса, ең үлкен антижелінің және ең кішкентай тізбектерге жіктеудің мөлшері қайтадан тең болады.
An antichain in a partially ordered set is a set of elements no two of which are comparable to each other, and a chain is a set of elements every two of which are comparable. A chain decomposition is a partition of the elements of the order into disjoint chains. Dilworth's theorem states that, in any finite partially ordered set, the largest antichain has the same size as the smallest chain decomposition. Here, the size of the antichain is its number of elements, and the size of the chain decomposition is its number of chains. The width of the partial order is defined as the common size of the antichain and chain decomposition. A version of the theorem for infinite partially ordered sets states that, when there exists a decomposition into finitely many chains, or when there exists a finite upper bound on the size of an antichain, the sizes of the largest antichain and of the smallest chain decomposition are again equal.
Индуктивті дәлелдеу
Қиссалық реттелген жиынның өлшемі бойынша индукция арқылы келесі дәлелдеме, осыған негізделген. Let be a finite partially ordered set болсын. Жиын бос болса, теорема тривиальды түрде орындалады. Демек, жиынның кем дегенде бір элементі бар деп есептейік, және ол жиынның максималды элементі болсын. Индукция бойынша, белгілі бір бүтін сан үшін ішінара реттелген жиынды қамтуға болатын ажыратылған тізбектер бар және кем дегенде бір антицепочка өлшемі бар деп есептейік. үшін, өлшемі бар антицепочкаға жататын жиындағы максималды элементті деп белгілейміз және қоямыз. Бұл антицепочка екенін дәлелдейміз. өлшемі бар және кіретін антицепочка болсын. Кез келген екі түрлі индекстерді таңдайық және содан кейін. Онда, анықтамасы бойынша. Бұл, себебі. және ролін ауыстыру арқылы да солай болады. Бұл, антицепочка екенін көрсетеді. Енді қайтадан қарастырайық. Егер кейбір үшін болса, онда тізбек болады. Таңдау бойынша, өлшемі бар антицепочкасы жоқ. Индукция бойынша, өлшемі бар антицепочкасы болғандықтан, жиынды ажыратылған тізбектермен жабуға болады. Осылайша, жиынды ажыратылған тізбектермен жабуға болады, қажеттісінше. Келесі, егер әр үшін болса, онда (максималдылығы бойынша) өлшемі бар антицепочка болады. Енді жиынды тізбектермен жабуға болады, дәлелдемені аяқтайды.
Let be a finite partially ordered set. The theorem holds trivially if is empty. So, assume that has at least one element, and let be a maximal element of
By induction, we assume that for some integer the partially ordered set can be covered by disjoint chains and has at least one antichain of size Clearly, for For , let be the maximal element in that belongs to an antichain of size in , and set
We claim that is an antichain. Let be an antichain of size that contains Fix arbitrary distinct indices and Then Let Then , by the definition of This implies that , since By interchanging the roles of and in this argument we also have This verifies that is an antichain. We now return to Suppose first that for some Let be the chain Then by the choice of , does not have an antichain of size Induction then implies that can be covered by disjoint chains since is an antichain of size in
Thus, can be covered by disjoint chains, as required. Next, if for each , then is an antichain of size in (since is maximal in ). Now can be covered by the chains , completing the proof.
Кениг теоремасы арқылы дәлелдеу
Сияқты комбинаторикадағы басқа да көптеген нәтижелермен қатар, Дилворт теоремасы екібөлікті графқа сәйкестік табу туралы Кёниг теоремасына және оған байланысты бірнеше басқа теоремаларға, соның ішінде Холлдың үйлену теоремасына эквивалентті. n элементі бар S ішінара тәртібі үшін Дилворт теоремасын дәлелдеу үшін Кёниг теоремасын пайдаланып, G = (U,V,E) екібөлікті графыны анықтаңыз, мұнда U = V = S және (u,v) жиегі S-де u < v болғанда G-де болады. Кёниг теоремасы бойынша, G-де M сәйкестігі және C түйіндерінің жиыны бар, мұнда графтың әрбір жиегінде C-де кем дегенде бір түйін бар және M мен C бірдей кардиналдыққа ие. A жиыны S элементтерінен тұрады, олар C-дегі ешбір түйінге сәйкес келмейді; онда A-да кем дегенде n – m элемент бар (егер C екі бөліктің екі жағындағы бір элементке сәйкес түйіндерді қамтыса, одан да көп болуы мүмкін) және A-ның ешбір екі элементі бір-бірімен салыстырылмайды. M-де (x, y) жиегі болғанда x және y бір тізбекке қосылатын тізбектер жиыны P болсын; онда P-де n – m тізбек болады. Сондықтан біз антижеліні және бірдей кардиналдықтағы тізбектерге бөлінуді құрдық. Дилворт теоремасынан Кёниг теоремасын дәлелдеу үшін, G = (U,V,E) екібөлікті графы үшін, G түйіндерінің ішінара тәртібін u < v дәл u U-да, v V-да және E-де u-дан v-ға жиек болғанда қалыптастырамыз. Дилворт теоремасы бойынша, A антижелісі және P тізбектеріне бөліну бар, екеуінің де мөлшері бірдей. Бірақ ішінара тәртіптегі тривиальды емес тізбектер ғана графтың жиектеріне сәйкес келетін элементтер жұбы, сондықтан P-дегі тривиальды емес тізбектер графтың сәйкестігін құрайды. A-ның толықтыруы G-де осы сәйкестікке сәйкес келетін бірдей кардиналдықтағы түйін жабыны құрайды. Бұл екібөлікті сәйкестікке байланысты кез келген ішінара тәртіптің енін полиномиалдық уақытта есептеуге мүмкіндік береді. Нақтырақ айтқанда, ені k n элементтік ішінара тәртіптерді O(kn²) уақытында тануға болады.
To prove Dilworth's theorem for a partial order S with n elements, using Kőnig's theorem, define a bipartite graph G = (U,V,E) where U = V = S and where (u,v) is an edge in G when u < v in S. By Kőnig's theorem, there exists a matching M in G, and a set of vertices C in G, such that each edge in the graph contains at least one vertex in C and such that M and C have the same cardinality m. Let A be the set of elements of S that do not correspond to any vertex in C; then A has at least n m elements (possibly more if C contains vertices corresponding to the same element on both sides of the bipartition) and no two elements of A are comparable to each other. Let P be a family of chains formed by including x and y in the same chain whenever there is an edge (x,y) in M; then P has n m chains. Therefore, we have constructed an antichain and a partition into chains with the same cardinality. To prove Kőnig's theorem from Dilworth's theorem, for a bipartite graph G = (U,V,E), form a partial order on the vertices of G in which u < v exactly when u is in U, v is in V, and there exists an edge in E from u to v. By Dilworth's theorem, there exists an antichain A and a partition into chains P both of which have the same size. But the only nontrivial chains in the partial order are pairs of elements corresponding to the edges in the graph, so the nontrivial chains in P form a matching in the graph. The complement of A forms a vertex cover in G with the same cardinality as this matching. This connection to bipartite matching allows the width of any partial order to be computed in polynomial time. More precisely, n element partial orders of width k can be recognized in time O(kn2) .
Шексіз ішінара реттелген жиынтықтарды кеңейту
Дилворттың шексіз ішінара реттелген жиындар туралы теоремасы бойынша, ішінара реттелген жиын w еніне ие, егер және ғана егер оны w тізбекке бөлуге болады. Яғни, егер шексіз ішінара реттілік P-нің ені w болса, онда кез келген антижеліде w элементтен аспайтын шекті сан бар. P-нің кез келген S ішкі жиыны үшін w тізбекке жіктеу (егер ол болса) S-тің салыстырусыздық графигін (S элементтері төбелері ретінде, әр екі салыстырылмайтын элемент арасында қабырғасы бар граф) w түспен бояу ретінде сипаттауға болады; салыстырусыздық графигінің дұрыс бояуындағы әрбір түс класы тізбек болуы керек. P-нің w ені бар деп есептесек және Дилворт теоремасының шекті нұсқасына сәйкес, P-нің кез келген шекті ішкі жиыны w түспен боялатын салыстырусыздық графигіне ие. Сондықтан, Де Брюйн-Эрдес теоремасы бойынша, P-нің өзі де w түспен боялатын салыстырусыздық графигіне ие, демек, қажетті тізбектерге жіктеуге ие. Дегенмен, теорема ені шексіз ішінара реттелген жиындарға осылай оңай қолданылмайды, тек жиынның кардиналдылығы ғана емес. Мұндай жағдайда ең үлкен антижелінің мөлшері мен ішінара реттілікті жабу үшін қажетті тізбектердің ең аз саны бір-бірінен өте өзгеше болуы мүмкін. Атап айтқанда, кез келген шексіз кардинал сан κ үшін, κ тізбекке жіктеуі бар, ені ℵ0 шексіз ішінара реттелген жиын бар. Бұл еңбек шексіз жағдайда Дилворт теоремасының аналогтарын талқылайды.
However, the theorem does not extend so simply to partially ordered sets in which the width, and not just the cardinality of the set, is infinite. In this case the size of the largest antichain and the minimum number of chains needed to cover the partial order may be very different from each other. In particular, for every infinite cardinal number κ there is an infinite partially ordered set of width ℵ0 whose partition into the fewest chains has κ chains
discusses analogues of Dilworth's theorem in the infinite setting.
Дилворт теоремасының (Мирский теоремасы) дуалы
Дилворт теоремасының дуалы былай гласиды: жартылай реттіліктегі ең үлкен тізбектің мөлшері (шекті болған жағдайда) реттілікті антижелілерге бөлуге қажетті ең кіші санына тең. Бұл дәлел Дилворт теоремасының дәлелінен әлдеқайда оңай: кез келген x элементі үшін, оны ең үлкен элементі ретінде қарастырып, N(x) осы x-ке максимальді тізбектердің ең үлкенінің мөлшерін белгілейік. Содан кейін N⁻¹(i), N-нің тең мәнін беретін элементтер жиыны, антижелі болып табылады, және осы антижелілер жартылай реттілікті ең үлкен тізбектің мөлшеріне тең антижелілер санына бөледі.
Салыстырмалылық графиктерінің жетілдірілуі
Салыстырмалылық графигі – тәртіптің әрбір элементі үшін төбе жасалып, кез келген екі салыстырылатын элементті қосатын қабырға арқылы жартылай тәртіптен құрылған бағытталмаған график. Осылайша, салыстырмалылық графигіндегі толық подграф тізбекке сәйкес келеді, ал тәуелсіз жиын антитізбекке сәйкес келеді. Салыстырмалылық графигінің кез келген индуцирленген субграфигі – бұл оның элементтерінің ішкі жиынына тәртіптің шектелуінен құрылған салыстырмалылық графигі. Егер әрбір индуцирленген субграфигіндегі түстік саны ең ірі толық подграфтың мөлшеріне тең болса, онда бағытталмаған граф кемелді болады. Кез келген салыстырмалылық граф кемелді болады: бұл негізінен Мирский теоремасы, граф теориясының терминдерімен қайта айтылған. Кемелді графтар теоремасы бойынша, кез келген кемелді графтың толықтырылысы да кемелді болады. Сондықтан, кез келген салыстырмалылық графтың толықтырылысы кемелді; бұл негізінен Дилворт теоремасы, граф теориясының терминдерімен қайта айтылған. Осылайша, кемелді графтардың толықтыру қасиеті Дилворт теоремасының баламалы дәлелін ұсынуы мүмкін.
Арнайы ішінара тапсырыстардың ені
Бульдық тор Bn – n элементті жиынның қуат жиыны X, негізінен {1, 2, …, n}, кіріктіру арқылы реттелген немесе, белгілену бойынша, (2[n], ⊆). Спернер теоремасы Bn-нің максималды антижелісінің мөлшері ең көп дегенде деп мәлімдейді.
Басқаша айтқанда, X-тің салыстырылмайтын ішкі жиындарының ең үлкен отбасы X-тің медианалық мөлшердегі ішкі жиындарын таңдау арқылы алынады. Любелл–Ямамото–Мешалькин теңсіздігі де қуат жиынындағы антижелілерге қатысты және оны Спернер теоремасын дәлелдеу үшін қолдануға болады. Егер [1, 2n] аралығындағы бүтін сандарды бөлінбелілік бойынша реттесек, [n + 1, 2n] аралық n кардиналдылығы бар антижелі құрайды. Бұл ішінара реттілікті n тізбекке бөлу оңай: [1, 2n] аралығындағы әрбір тақ сан m үшін m2i түріндегі сандар тізбегін құраңыз. Сондықтан Дилворт теоремасы бойынша, бұл ішінара реттіліктің ені n-ге тең.
Эрдёш–Секереш теоремасы монотонды кіші тізбектер туралы, Дилворт теоремасын екінші өлшемдегі ішінара реттіліктерге қолдану ретінде қарастырылуы мүмкін. Антиматроидтың "дөңес өлшемі" антиматроидты анықтау үшін қажетті тізбектердің ең аз саны ретінде анықталады, ал Дилворт теоремасын оның байланысты ішінара реттіліктің еніне тең екенін көрсетуге болады; бұл байланыс дөңес өлшемді табуға арналған полиномиалдық уақыт алгоритміне әкеледі.
The "convex dimension" of an antimatroid is defined as the minimum number of chains needed to define the antimatroid, and Dilworth's theorem can be used to show that it equals the width of an associated partial order; this connection leads to a polynomial time algorithm for convex dimension .