- Теорема Дилуорса
-
Теорема Дилуорса в комбинаторике — утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств.
Содержание
Формулировка
Пусть — наибольшее количество элементов антицепи (англ. antichain) данного конечного частично упорядоченного множества . Тогда можно разбить на попарно непересекающихся цепей.
Другими словами, минимальное число непересекающихся цепей, которые в совокупности содержат все элементы частично упорядоченного множества , равно максимально возможному числу элементов в подмножестве множества , состоящем из попарно несравнимых элементов, если это число конечно[1].
Примечания
Два элемента частично упорядоченного множества называются сравнимыми, если они образуют цепь, в противном случае они называются несравнимыми[1].
Доказательство
Теорема была доказана американским математиком Робертом Дилуорсом (англ. Robert P. Dilworth), (1914—1993), главной областью исследований которого была теория решёток.
Литература
- ↑ 1 2 Маршалл Холл Младший Комбинаторика = Combinatorial Theory. — "МИР", 1970. — С. 90-94.
- Berge, Claude & Chvátal, Václav (1984), «Topics on Perfect Graphs», vol. 21, Annals of Discrete Mathematics, Elsevier, с. viii, ISBN 9780444865878
- Dilworth, Robert P. (1950), "«A Decomposition Theorem for Partially Ordered Sets»", Annals of Mathematics Т. 51 (1): 161–166, doi:10.2307/1969503, <http://jstor.org/stable/1969503>.
- Edelman, Paul H. & Saks, Michael E. (1988), "«Combinatorial representation and convex dimension of convex geometries»", Order Т. 5 (1): 23–32, DOI 10.1007/BF00143895.
- Fulkerson, D. R. (1956), "«Note on Dilworth’s decomposition theorem for partially ordered sets»", Proceedings of the American Mathematical Society Т. 7 (4): 701–702, <http://www.jstor.org/stable/2033375>.
- Galvin, Fred (1994), "«A proof of Dilworth's chain decomposition theorem»", The American Mathematical Monthly Т. 101 (4): 352–353, MR1270960, doi:10.2307/2975628, <http://jstor.org/stable/2975628>.
- Lovász, László (1972), "«Normal hypergraphs and the perfect graph conjecture»", Discrete Mathematics Т. 2: 253–267, DOI 10.1016/0012-365X(72)90006-4.
- Mirsky, Leon (1971), "«A dual of Dilworth's decomposition theorem»", American Mathematical Monthly Т. 78 (8): 876–877, doi:10.2307/2316481, <http://jstor.org/stable/2316481>.
- Perles, Micha A. (1963), "«On Dilworth's theorem in the infinite case»", Israel Journal of Mathematics Т. 1: 108–109, MR0168497, DOI 10.1007/BF02759806.
- Steele, J. Michael (1995), "Variations on the monotone subsequence theme of Erdős and Szekeres", in Aldous, David; Diaconis, Persi & Spencer, Joel et al., «Discrete Probability and Algorithms», vol. 72, IMA Volumes in Mathematics and its Applications, Springer-Verlag, сс. 111–131, <http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf>.
Ссылки
- А. В. Спивак, Цепи и антицепи, Московский центр непрерывного математического образования, материалы занятий выездной математической школы 7-11.04.2004.]
- Equivalence of seven major theorems in combinatorics
- Dual of Dilworth's Theorem. PlanetMath.
- Babai, László Lecture notes in Combinatorics and Probability, Lecture 10: Perfect Graphs (2005). Архивировано из первоисточника 14 мая 2012.
- Felsner, S., Raghavan, V., and Spinrad, J. Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number (1999). Архивировано из первоисточника 14 мая 2012.
- Weisstein, Eric W. Dilworth's Lemma (англ.) на сайте Wolfram MathWorld.
Категории:- Теория порядка
- Теория графов
- Теоремы
Wikimedia Foundation. 2010.