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

Теорема Дилуорса — комбинаторное утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств: конечное частично упорядоченное множество ${\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^−1(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^i. Таким образом, по теореме Дилуорса, ширина этого частичного порядка равна n.

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

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

Примечания

1. Маршалл Холл Младший. Комбинаторика = Combinatorial Theory. — "МИР", 1970. — С. 90—94. Архивировано 14 октября 2011 года.
2. Galvin, 1994.
3. Fulkerson, 1956.
4. Harzheim, 2005.
5. Perles, 1963.
6. Mirsky, 1971.
7. Berge, Chvátal, 1984.
8. Lovász, 1972.
9. Steele, 1995.
10. Edelman, Saks, 1988.

Литература

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