Теорема Ділворса
У математиці, в таких галузях, як теорія порядку та комбінаторика, Теорема Ділворса характеризує ширину довільної скінченної частково впорядкованої множини у термінах розбиття цього порядку на найменше число ланцюгів. Названа на честь математика Роберта П. Ділворса.
Антиланцюг у частково впорядкованій множині є множина елементів, будь-які два з яких не є порівнювані, і ланцюг є множина елементів, кожні два з яких є порівнювані. Теорема Ділворса стверджує, що існує антиланцюг 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.
- Babai, László (2005). Lecture notes in Combinatorics and Probability, Lecture 10: Perfect Graphs (PDF). Архів (PDF) оригіналу за 14 травня 2012. Процитовано 29 січня 2010.
- Felsner, S., Raghavan, V., and Spinrad, J. (1999). Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number. Архів оригіналу за 14 травня 2012. Процитовано 29 січня 2010.
- Weisstein, Eric W. Dilworth's Lemma. MathWorld–A Wolfram Web Resource.
 | В іншому мовному розділі є повніша стаття Dilworth's theorem(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської.
|