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

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

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

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

Примечания

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

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

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

Литература

• Berge, Claude & Chvátal, Václav (1984), Topics on Perfect Graphs, vol. 21, Annals of Discrete Mathematics, Elsevier, p. viii, ISBN 9780444865878 
• A Decomposition Theorem for Partially Ordered Sets", 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 .
• Note on Dilworth’s decomposition theorem for partially ordered sets", http://www.jstor.org/stable/2033375> .
• A proof of Dilworth's chain decomposition theorem", 1270960, 10.2307/2975628, <http://jstor.org/stable/2975628> .
• 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", 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, 0168497, DOI 10.1007/BF02759806 .
• "Variations on the monotone subsequence theme of Erdős and Szekeres", in http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf> .