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

Теорема Дилуорса — комбинаторное утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств: конечное частично упорядоченное множество ${\displaystyle A}$ может быть разбито на ${\displaystyle n}$ попарно непересекающихся цепей, где ${\displaystyle n}$ — количество элементов наибольшей антицепи множества ${\displaystyle A}$^[1] (называемое также шириной частично упорядоченного множества).

Версия теоремы для бесконечных частично упорядоченных множеств: частично упорядоченное множество имеет конечную ширину ${\displaystyle w}$ тогда и только тогда, когда его можно разбить на ${\displaystyle w}$ цепей, но не меньше.

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

Доказательство по индукции по размеру частично упорядоченного множества ${\displaystyle M}$ основывается на доказательстве Галвина^[2].

Пусть ${\displaystyle M}$ — конечное частично упорядоченное множество. Утверждение тривиально, если ${\displaystyle M}$ пусто. Так что предположим, что ${\displaystyle M}$ имеет как минимум один элемент, и пусть ${\displaystyle a}$ — максимальный элемент ${\displaystyle M}$.

По предположению индукции, для некоторого целого ${\displaystyle k}$ частично упорядоченное множество ${\displaystyle M':=M\setminus \{a\}}$ можно покрыть ${\displaystyle k}$ непересекающимися цепями ${\displaystyle C_{1},\dots ,C_{k}}$ и имеет по меньшей мере одну антицепь ${\displaystyle A_{0}}$ размера ${\displaystyle k}$. Ясно, что ${\displaystyle A_{0}\cap C_{i}\neq \emptyset }$ для ${\displaystyle i=1,2,\dots ,k}$. Для ${\displaystyle i=1,2,\dots ,k}$ пусть ${\displaystyle x_{i}}$ — максимальный элемент в ${\displaystyle C_{i}}$, который принадлежит какой-либо антицепи размера ${\displaystyle k}$ в ${\displaystyle M'}$, и множество ${\displaystyle A:=\{x_{1},x_{2},\dots ,x_{k}\}}$. Докажем, что ${\displaystyle A}$ — антицепь. Пусть ${\displaystyle A_{i}}$ — антицепь размера ${\displaystyle k}$, содержащая ${\displaystyle x_{i}}$. Зафиксируем произвольные различные индексы ${\displaystyle i}$ и ${\displaystyle j}$. Тогда ${\displaystyle A_{i}\cap C_{j}\neq \emptyset }$. Пусть ${\displaystyle y\in A_{i}\cap C_{j}}$. Тогда ${\displaystyle y\leq x_{j}}$ по определению ${\displaystyle x_{j}}$. Отсюда следует, что ${\displaystyle x_{i}\not \geq x_{j}}$, поскольку ${\displaystyle x_{i}\not \geq y}$. Если обменять роли ${\displaystyle i}$ и ${\displaystyle j}$, мы получим ${\displaystyle x_{j}\not \geq x_{i}}$. Это доказывает, что ${\displaystyle A}$ является антицепью.

Вернёмся к ${\displaystyle M}$. Предположим сначала, что ${\displaystyle a\geq x_{i}}$ для некоторого ${\displaystyle i\in \{1,2,\dots ,k\}}$. Пусть ${\displaystyle K}$ — цепь ${\displaystyle \{a\}\cup \{z\in C_{i}:z\leq x_{i}\}}$. Тогда вследствие выбора ${\displaystyle x_{i}}$ ${\displaystyle M\setminus K}$ не содержит антицепь размера ${\displaystyle k}$. Из предположения индукции следует, что ${\displaystyle M\setminus K}$ можно покрыть ${\displaystyle k-1}$ непересекающимися цепями, поскольку ${\displaystyle A\setminus \{x_{i}\}}$ является антицепью размера ${\displaystyle k-1}$ в ${\displaystyle M\setminus K}$. Таким образом, ${\displaystyle M}$ можно покрыть ${\displaystyle k}$ непересекающимися цепями, что и требовалось.

Теперь, если ${\displaystyle a\not \geq x_{i}}$ для каждого ${\displaystyle i\in \{1,2,\dots ,k\}}$, то ${\displaystyle A\cup \{a\}}$ является антицепью размера ${\displaystyle k+1}$ в ${\displaystyle M}$ (поскольку ${\displaystyle a}$ — максимальное в ${\displaystyle M}$). Таким образом, ${\displaystyle M}$ может быть покрыто ${\displaystyle k+1}$ цепями ${\displaystyle \{a\},C_{1},C_{2},\dots ,C_{k}}$, что завершает доказательство.

Подобно другим результатам комбинаторики теорема Дилуорса эквивалентна теореме Кёнига о паросочетаниях на двудольных графах и некоторым другим теоремам, включая теорему Холла о свадьбах^[3].

Для доказательства теоремы Дилуорса для частично упорядоченного множества S с n элементами, используя теорему Кёнига, определим двудольный граф G = (U,V,E), где U = V = S и (u,v) является ребром в G, если u < v в S. По теореме Кёнига существует паросочетание M в G, и множество вершин C в G, такие, что каждое ребро из графа содержит, по крайней мере, одну вершину из C и оба множества, M и C, имеют одно и то же число элементов m. Пусть A — множество элементов S, которым не соответствует никакая вершина в C. Тогда A имеет как минимум n — m элементов (возможно больше, если C содержит вершины, соответствующие одному и тому же элементу на обеих сторонах двудольного графа). Пусть P — семейство цепей, образованных включением x и y в одну цепочку, когда существует ребро (x,y) в M. Тогда P имеет n — m цепей. Таким образом, мы сконструировали антицепь и разложение на цепи с тем же числом элементов в множестве.

Для доказательства теоремы Кёнига из теоремы Дилуорса для двудольного графа G = (U,V,E) образуем частичный порядок на вершинах графа G, полагая u < v в точности, когда u содержится в U, v содержится V и существует ребро из E из u в v. По теореме Дилуорса существует антицепь A и разложение на цепи P, оба множества одного размера. Но нетривиальными цепями в частичном порядке могут быть только пары элементов, соответствующих рёбрам графа, так что нетривиальные цепи из P образуют паросочетание в графе. Дополнение A образует покрытие вершин G с тем же числом элементов, что и в паросочетании.

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

Теорема Дилуорса для неограниченных частично упорядоченных множеств утверждает, что такое множество имеет ограниченную ширину w в том и только в том случае, когда оно может быть разложено на w цепей. Предположим, что бесконечное частично упорядоченное множество P имеет ширину w, что означает, что любая антицепь содержит не более конечного числа w элементов. Для любого подмножества S множества P разложение на w цепей (если существует) можно описать как раскраска графа несравнимости S (граф, имеющий элементы S в качестве вершин и рёбра для несравнимых вершин), используя w цветов. Любой класс расцветки графа несравнимости должен быть цепью. В предположении, что P имеет ширину w, по версии теоремы Дилуорса для конечного случая, любое конечное подмножество S множества P имеет w-цветную раскраску графа несравнимости. Таким образом, по теореме де Брейна — Эрдёша, P сам также имеет w-цветную раскраску графа несравнимости, а это есть желаемое разделение на цепи^[4].

Однако теорема не обобщается так просто на случай для частично упорядоченных множеств, когда ширина не ограничена. В этом случае размер максимальной антицепи и минимального числа цепей, необходимых для покрытия, могут существенно отличаться. В частности, для любого бесконечного кардинального числа κ существует бесконечное частично упорядоченное множество с шириной ℵ₀, разделение которого на цепи имеет не меньше κ цепей^[4].

В 1963 году^[5] получено аналогичное теореме Дилуорса утверждение для неограниченного случая.

Теорема, двойственная теореме Дилуорса — теорема Мирского, — утверждает, что размер наибольшей цепи в частичном порядке (конечный случай) равен наименьшему числу антицепей, на которые можно разложить частичный порядок^[6]. Доказательство этой теоремы много проще доказательства теоремы Дилуорса. Для любого элемента x возьмём цепи, имеющие x в качестве максимального элемента, и пусть N(x) означает размер наибольшей из этих x-максимальных цепей. Тогда каждое множество N⁻¹(i), состоящее из элементов, которые имеют одинаковые значения N, является антицепью, и размер этого разделения частично упорядоченного множества на антицепи равно размеру наибольшей цепи.

Граф сравнимости — это неориентированный граф, образованный из частичного порядка путём создания вершин для каждого элемента порядка и рёбер для любых двух сравнимых элементов. Таким образом, клика в графе сравнимости соответствует цепи, а независимое множество соответствует антицепи. Любой Порождённый подграф графа сравнимости сам является графом сравнимости, образованным из частичного порядка путём сужения на подмножество элементов.

Неориентированный граф является совершенным, если в каждом порождённом подграфе хроматическое число равно размеру наибольшей клики. Любой граф сравнимости является совершенным — это как раз теорема Мирского, пересказанная в терминах теории графов^[7]. По теореме о совершенных графах Ловаса^[8], дополнение любого совершенного графа является также совершенным графом. Таким образом, дополнение любого графа сравнимости является совершенным. Это, по существу, та же теорема Дилуорса, сформулированная в терминах теории графов^[7]. Таким образом, свойство дополнительности совершенных графов может дать альтернативное доказательство теоремы Дилуорса.

Булевская решётка B_n — это степень множества X из n элементов — скажем, {1, 2, …, n} — упорядоченное по включению, или, формально, (2^[n], ⊆). Теорема Шпернера^[англ.] утверждает, что максимальная антицепь в B_n имеет размер, не превосходящий

${\displaystyle {\mbox{width}}(B_{n})={n \choose \lfloor {n/2}\rfloor }.}$

Другими словами, наибольшее семейство подмножеств несравнимости множеств X получается выбором подмножеств X, которые имеют среднее значение. Неравенство Любелла–Ямамото–Мешалкина^[англ.] также имеет отношение к антицепям в степенях множества и может быть использовано для доказательства теорема Спернера.

Если упорядочить целые числа в интервале [1, 2n] по делимости, подынтервал [n + 1, 2n] образует антицепь размером n. Разложение этого частичного порядка на n цепей легко получить: для каждого нечётного m в [1,2n] образуем цепь из чисел вида m2ⁱ. Таким образом, по теореме Дилуорса, ширина этого частичного порядка равна n.

Теорему Эрдёша — Секереша о монотонных подпоследовательностях можно интерпретировать как приложение теоремы Дилуорса к частичным порядкам размерности^[англ.] два^[9].

«Выпуклая размерность» антиматроида^[англ.] определяется как минимальное число цепей, необходимых для определения антиматроида, и теорему Дилуорса можно использовать, чтобы показать, что она равна ширине связанного частичного порядка. Эта связь приводит к линейному по времени работы алгоритму для поиска выпуклой размерности^[10].

• Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Heidelberg: Springer, 2012. — Т. 28. — С. 42. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4.
• Egbert Harzheim. Ordered sets. — New York: Springer, 2005. — Т. 7. — С. Theorem 5.6, p.60. — (Advances in Mathematics (Springer)). — ISBN 0-387-24219-8.
• Claude Berge, Václav Chvátal. Topics on Perfect Graphs. — Elsevier, 1984. — Т. 21. — С. viii. — ISBN 9780444865878.
• Robert P. Dilworth. A Decomposition Theorem for Partially Ordered Sets // Annals of Mathematics. — 1950. — Т. 51, вып. 1. — С. 161—166. — doi:10.2307/1969503.
• Paul H. Edelman, Michael E. Saks. Combinatorial representation and convex dimension of convex geometries // Order. — 1988. — Т. 5, вып. 1. — С. 23—32. — doi:10.1007/BF00143895.
• D. R. Fulkerson. Note on Dilworth’s decomposition theorem for partially ordered sets (англ.) // Proceedings of the American Mathematical Society. — 1956. — Vol. 7, iss. 4. — P. 701—702.
• Fred Galvin. A proof of Dilworth's chain decomposition theorem // The American Mathematical Monthly. — 1994. — Т. 101, вып. 4. — С. 352—353. — doi:10.2307/2975628.
• László Lovász. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics. — 1972. — Т. 2. — С. 253—267. — doi:10.1016/0012-365X(72)90006-4.
• Leon Mirsky. A dual of Dilworth's decomposition theorem // American Mathematical Monthly. — 1971. — Т. 78, вып. 8. — С. 876—877. — doi:10.2307/2316481..
• Micha A. Perles. On Dilworth's theorem in the infinite case // Israel Journal of Mathematics. — 1963. — Т. 1. — С. 108—109. — doi:10.1007/BF02759806.
• J. Michael Steele. Discrete Probability and Algorithms / David Aldous, Persi Diaconis, Joel Spencer, J. Michael Steele. — Springer-Verlag, 1995. — Т. 72. — С. 111–131. — (IMA Volumes in Mathematics and its Applications).
• А. В. Спивак, Цепи и антицепи, Московский центр непрерывного математического образования, материалы занятий выездной математической школы 7-11.04.2004.]
• Equivalence of seven major theorems in combinatorics
• Dual of Dilworth's Theorem  (неопр.). PlanetMath. Дата обращения: 12 июня 2011. Архивировано из оригинала 14 июля 2007 года.
• Babai, László. Lecture notes in Combinatorics and Probability, Lecture 10: Perfect Graphs  (неопр.) (2005). Дата обращения: 12 июня 2011. Архивировано 14 мая 2012 года.
• Felsner, S., Raghavan, V., and Spinrad, J. Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number  (неопр.) (1999). Дата обращения: 12 июня 2011. Архивировано 14 мая 2012 года.
• Weisstein, Eric W. Dilworth’s Lemma (англ.) на сайте Wolfram MathWorld.