У математиці, в таких галузях, як теорія порядку та комбінаторика, Теорема Ділворса характеризує ширину довільної скінченної частково впорядкованої множини у термінах розбиття цього порядку на найменше число ланцюгів. Названа на честь математика .
Антиланцюг у частково впорядкованій множині є множина елементів, будь-які два з яких не є порівнювані, і ланцюг є множина елементів, кожні два з яких є порівнювані. Теорема Ділворса стверджує, що існує антиланцюг 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.
Посилання
- (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.
В іншому мовному розділі є повніша стаття Dilworth's theorem(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської.
|
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет