WikiSort.ru - Не сортированное

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

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

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

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

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

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

Эквивалентная формулировка теоремы Дилуорса утверждает, что в любом конечном частично упорядоченном множестве максимальное число элементов в любой антицепи равно минимальному числу разбиения множества на цепи. Версия теоремы для бесконечных частично упорядоченных множеств утверждает, что частично упорядоченное множество имеет конечную ширину w тогда и только тогда, когда его можно разбить на w цепей, но не меньше.

Доказательство по индукции

Следующее доказательство по индукции по размеру частично упорядоченного множества ${\displaystyle M}$ основывается на доказательстве Галвина (Galvin 1994).

Пусть ${\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}}$ , что завершает доказательство.

Доказательство через теорему Кёнига

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

Для доказательства теоремы Дилуорса для частично упорядоченного множества 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-цветную раскраску графа несравнимости. Таким образом, по теореме де Брейна–Эрдёша^[en], P сам также имеет w-цветную раскраску графа несравнимости, а это есть желаемое разделение на цепи (Harzheim 2005).

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

Перлес (Perles 1963) рассматривает аналогичную теореме Дилуорса теорему для неограниченного случая.

Теорема, двойственная теореме Дилуорса (теорема Мирского^[en])

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

Совершенство графов сравнимости

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

Неориентированный граф является совершенным, если в каждом порождённом подграфе хроматическое число равно размеру наибольшей клики. Любой граф сравнимости является совершенным — это как раз теорема Мирского, пересказанная в терминах теории графов (Berge, Chvátal 1984). По теореме о совершенных графах Ловаса (Lovász 1972), дополнение любого совершенного графа является также совершенным графом. Таким образом, дополнение любого графа сравнимости является совершенным. Это, по существу, та же теорема Дилуорса, сформулированная в терминах теории графов (Berge, Chvátal 1984). Таким образом, свойство дополнительности совершенных графов может дать альтернативное доказательство теоремы Дилуорса.

Ширина специальных частичных порядков

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

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

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

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

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

«Выпуклая размерность» антиматроида^[en] определяется как минимальное число цепей, необходимых для определения антиматроида, и теорему Дилуорса можно использовать, чтобы показать, что она равна ширине связанного частичного порядка. Эта связь приводит к линейному по времени работы алгоритму для поиска выпуклой размерности (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. — Т. 7, вып. 4. — С. 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.
• 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 года.
• не указан параметр |title =

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.