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

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

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

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.