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

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

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

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

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

Примечания

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

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

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

Литература

• 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.