У математиці в таких галузях як теорія порядку та комбінаторика Теорема Ділворса характеризує ширину довільної скінченно

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

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

. Dilworth's Lemma. MathWorld–A Wolfram Web Resource.