Теорема Ділуорса

У математиці, у таких галузях, як теорія порядку та комбінаторика, Теорема Ділуорса характеризує ширину довільної скінченної частково впорядкованої множини у термінах розбиття цього порядку на найменше число ланцюгів. Названа на честь математика Роберта П. Ділуорса.

Антиланцюг у частково впорядкованій множині є множина елементів будь-які два з яких не є порівнювані, і ланцюг є множина елементів кожні два з яких є порівнювані. Теорема Ділуорса стверджує, що існує антиланцюг A, і розбиття даного порядку, що являє собою сімейство P ланцюгів, такі, що число ланцюгів у розбитті дорівнює потужності A. Коли це виконується, A повинен бути найбільшим антиланцюгом у порядку, оскільки будь-який антиланцюг не може мати більне одно елемента від кожного представника P. Аналогічно, P має бути найменшим сімейством ланцюгів, що являє собою розбиття даного порядку, оскільки будь-яке розбиття на ланцюги мусить мати принаймні один ланцюг для кожного елементу з A. Ширина часткового порядку визначається як спільний розмір A та P.

Еквівалентне формулювання Теореми Ділуорса таке, у довільній частково впорядкованій множині, найбільше число елементів у будь-якому антиланцюзі дорівнює найменшому числу ланцюгів у будь-якому розбитті даної множини на ланцюги.

Посилання

• Dilworth, Robert P. (1950), «A Decomposition Theorem for Partially Ordered Sets», Annals of Mathematics 51: 161–166, doi:10.2307/1969503 .

• Galvin, Fred (1994), «A proof of Dilworth's chain decomposition theorem», The American Mathematical Monthly 101 (4): 352–353, doi:10.2307/2975628, MR1270960 .

• Mirsky, Leon (1971), «A dual of Dilworth's decomposition theorem», American Mathematical Monthly 78: 876–877, doi:10.2307/2316481 .

• Perles, Micha A. (1963), «On Dilworth's theorem in the infinite case», Israel Journal of Mathematics 1: 108–109, doi:10.1007/BF02759806, MR0168497 .

Зовнішні посилання

• Equivalence of seven major theorems in combinatorics

• «Dual of Dilworth's Theorem». PlanetMath. 

• Babai, László (2005). «Lecture notes in Combinatorics and Probability, Lecture 10: Perfect Graphs». 

• Felsner, S., Raghavan, V., and Spinrad, J. (1999). «Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number». 

• Weisstein, Eric W. «Dilworth's Lemma». MathWorld–A Wolfram Web Resource.