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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Формулировка[править | править вики-текст]

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

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

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

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

Доказательство по индукции[править | править вики-текст]

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

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

По предположению индукции, для некоторого целого k частично упорядоченное множество M':=M\setminus\{a\} можно покрыть k непересекающимися цепями C_1,\dots,C_k и имеет по меньшей мере одну антицепь A_0 размера k. Ясно, что A_0\cap C_i\ne\emptyset для i=1,2,\dots,k. Для i=1,2,\dots,k пусть x_i — максимальный элемент в C_i, который принадлежит цепи размера k в M' и множеству A:=\{x_1,x_2,\dots,x_k\}. Мы утверждаем, что A — антицепь. Пусть A_i — антицепь размера k, содержащая x_i. Зафиксируем произвольные различные индексы i и j. Тогда A_i\cap C_j\ne\emptyset. Пусть y\in A_i\cap C_j. Тогда y\le x_j по определению x_j. Отсюда следует, что x_i\not \ge x_j, поскольку x_i\not\ge y. Если обменять роли i и j, мы получим x_j\not\ge x_i. Это доказывает, что A является антицепью.

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

Теперь, если a\not\ge x_i для каждого i\in\{1,2,\dots,k\}, то A\cup\{a\} является антицепью размера k+1 в M (поскольку a — максимальное в M). Таким образом, M может быть покрыто k+1 цепями \{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).

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

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

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

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

Совершенство графов сравнимости[править | править вики-текст]

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

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

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

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

\mbox{width}(B_n) = {n \choose \lfloor{n/2}\rfloor}.

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

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

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

"Выпуклая размерность" антиматроида[en] опредляется как минимальное число цепей, необходимых для определения антиматроида и теорему Дилуорса можно использовать, чтобы показать, что она равна ширине связанного частичного порядка. Эта связь приводит к линейному по времени работы алгоритму для поиска выпуклой размерности (Edelman, Saks 1988).

Литература[править | править вики-текст]

  1. 1 2 Маршалл Холл Младший Комбинаторика = Combinatorial Theory. — "МИР", 1970. — С. 90-94.
  • 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. — В. 1. — Т. 51. — С. 161–166. — DOI:10.2307/1969503.
  • Paul H. Edelman, Michael E. Saks Combinatorial representation and convex dimension of convex geometries // Order. — 1988. — В. 1. — Т. 5. — С. 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. — В. 4. — Т. 7. — С. 701–702..
  • Fred Galvin A proof of Dilworth's chain decomposition theorem // The American Mathematical Monthly. — 1994. — В. 4. — Т. 101. — С. 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. — В. 8. — Т. 78. — С. 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)..