Дилуорса теорема

Теорема Дилуорса в комбинаторике — утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств.

Формулировака

Пусть n — наибольшее количество элементов антицепи (англ. antichain) данного конечного частично упорядоченного множества M. Тогда M можно разбить на n попарно непересекающихся цепей.

Другими словами, минимальное число непересекающихся цепей, которые в совокупности содержат все элементы частично упорядоченного множества M, равно максимально возможному числу элементов в подмножестве множества M, состоящем из попарно несравнимых элементов, если это число конечно^[1].

Примечания

Два элемента частично упорядоченного множества называются сравнимыми, если они образуют цепь, в противном случае они называются несравнимыми^[1].

Доказательство

Теорема была доказана американским математиком Робертом Дилуорсом (англ. Robert P. Dilworth), (1914—1993), главной областью исследований которого была теория решёток.

Литература

1. ↑ ^{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, p. 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, pp. 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).
• Felsner, S., Raghavan, V., and Spinrad, J. Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number (1999).
• Weisstein, Eric W. Dilworth's Lemma (англ.) на сайте Wolfram MathWorld.