Введение
В математике, в областях теории порядка и комбинаторики, теорема Дилворта характеризует ширину любого конечного частично упорядоченного множества через разбиение порядка на минимальное число цепей. Она названа в честь математика Роберта Дилворта. Антицепь в частично упорядоченном множестве — это множество элементов, ни два из которых не сравнимы друг с другом, а цепь — это множество элементов, любые два из которых сравнимы. Разложение на цепи — это разбиение элементов порядка на непересекающиеся цепи. Теорема Дилворта утверждает, что в любом конечном частично упорядоченном множестве наибольшая антицепь имеет тот же размер, что и наименьшее разложение на цепи. Здесь размер антицепи — это число её элементов, а размер разложения на цепи — это число цепей. Ширина частичного порядка определяется как общий размер наибольшей антицепи и наименьшего разложения на цепи. Версия теоремы для бесконечных частично упорядоченных множеств утверждает, что если существует разложение на конечное число цепей, или если существует конечная верхняя граница на размер антицепи, то размеры наибольшей антицепи и наименьшего разложения на цепи снова равны.
An antichain in a partially ordered set is a set of elements no two of which are comparable to each other, and a chain is a set of elements every two of which are comparable. A chain decomposition is a partition of the elements of the order into disjoint chains. Dilworth's theorem states that, in any finite partially ordered set, the largest antichain has the same size as the smallest chain decomposition. Here, the size of the antichain is its number of elements, and the size of the chain decomposition is its number of chains. The width of the partial order is defined as the common size of the antichain and chain decomposition. A version of the theorem for infinite partially ordered sets states that, when there exists a decomposition into finitely many chains, or when there exists a finite upper bound on the size of an antichain, the sizes of the largest antichain and of the smallest chain decomposition are again equal.
Индуктивное доказательство
Следующее доказательство индукцией по размеру частично упорядоченного множества основано на доказательстве для случая Пусть будет конечным частично упорядоченным множеством. Теорема тривиально верна, если оно пусто. Итак, предположим, что содержит хотя бы один элемент, и пусть будет максимальным элементом в . По индукции предположим, что для некоторого целого числа частично упорядоченное множество можно покрыть непересекающимися цепочками и содержит хотя бы одну антицепь размера. Очевидно, для . Для , пусть будет максимальным элементом в , принадлежащим антицепи размера в , и определим .
Let be a finite partially ordered set. The theorem holds trivially if is empty. So, assume that has at least one element, and let be a maximal element of
By induction, we assume that for some integer the partially ordered set can be covered by disjoint chains and has at least one antichain of size Clearly, for For , let be the maximal element in that belongs to an antichain of size in , and set
We claim that is an antichain. Let be an antichain of size that contains Fix arbitrary distinct indices and Then Let Then , by the definition of This implies that , since By interchanging the roles of and in this argument we also have This verifies that is an antichain. We now return to Suppose first that for some Let be the chain Then by the choice of , does not have an antichain of size Induction then implies that can be covered by disjoint chains since is an antichain of size in
Thus, can be covered by disjoint chains, as required. Next, if for each , then is an antichain of size in (since is maximal in ). Now can be covered by the chains , completing the proof.
Утверждаем, что является антицепью. Пусть является антицепью размера, содержащей . Зафиксируем произвольные различные индексы и . Тогда пусть . Тогда , по определению . Это подразумевает, что , поскольку . Меняя местами роли и в этом аргументе, мы также получаем . Это подтверждает, что является антицепью. Теперь вернемся к . Предположим сначала, что для некоторого . Пусть будет цепочкой. Тогда, по выбору , не имеет антицепи размера . Индукция тогда подразумевает, что можно покрыть непересекающимися цепочками, поскольку является антицепью размера в .
Let be a finite partially ordered set. The theorem holds trivially if is empty. So, assume that has at least one element, and let be a maximal element of
By induction, we assume that for some integer the partially ordered set can be covered by disjoint chains and has at least one antichain of size Clearly, for For , let be the maximal element in that belongs to an antichain of size in , and set
We claim that is an antichain. Let be an antichain of size that contains Fix arbitrary distinct indices and Then Let Then , by the definition of This implies that , since By interchanging the roles of and in this argument we also have This verifies that is an antichain. We now return to Suppose first that for some Let be the chain Then by the choice of , does not have an antichain of size Induction then implies that can be covered by disjoint chains since is an antichain of size in
Thus, can be covered by disjoint chains, as required. Next, if for each , then is an antichain of size in (since is maximal in ). Now can be covered by the chains , completing the proof.
Таким образом, можно покрыть непересекающимися цепочками, как и требуется. Далее, если для каждого , то является антицепью размера в (поскольку максимальна в ). Теперь можно покрыть цепочками, завершая доказательство.
Let be a finite partially ordered set. The theorem holds trivially if is empty. So, assume that has at least one element, and let be a maximal element of
By induction, we assume that for some integer the partially ordered set can be covered by disjoint chains and has at least one antichain of size Clearly, for For , let be the maximal element in that belongs to an antichain of size in , and set
We claim that is an antichain. Let be an antichain of size that contains Fix arbitrary distinct indices and Then Let Then , by the definition of This implies that , since By interchanging the roles of and in this argument we also have This verifies that is an antichain. We now return to Suppose first that for some Let be the chain Then by the choice of , does not have an antichain of size Induction then implies that can be covered by disjoint chains since is an antichain of size in
Thus, can be covered by disjoint chains, as required. Next, if for each , then is an antichain of size in (since is maximal in ). Now can be covered by the chains , completing the proof.
Доказательство теоремы Кенига
Как и ряд других результатов в комбинаторике, теорема Дилворта эквивалентна теореме Кёнига о паросочетании в двудольном графе и нескольким другим связанным теоремам, включая теорему Холла о браке. Чтобы доказать теорему Дилворта для частичного порядка 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 содержит вершины, соответствующие одному и тому же элементу с обеих сторон двудольного разбиения), и никакие два элемента из A не сопоставимы друг с другом. Пусть P — семейство цепей, образованное включением x и y в одну и ту же цепь, когда в M есть ребро (x, y); тогда P содержит n - m цепей. Следовательно, мы построили антицепь и разбиение на цепи с одинаковой кардинальностью. Чтобы доказать теорему Кёнига из теоремы Дилворта, для двудольного графа G = (U, V, E) сформируем частичный порядок на вершинах G, в котором u < v тогда и только тогда, когда u находится в U, v находится в V, и существует ребро в E из u в v. По теореме Дилворта, существует антицепь A и разбиение на цепи P, оба из которых имеют одинаковый размер. Но единственными нетривиальными цепями в частичном порядке являются пары элементов, соответствующих рёбрам в графе, поэтому нетривиальные цепи в P образуют паросочетание в графе. Дополнение A образует вершинное покрытие в G с той же кардинальностью, что и это паросочетание. Эта связь с паросочетанием в двудольном графе позволяет вычислить ширину любого частичного порядка за полиномиальное время. Более точно, частичные порядки с n элементами и шириной k могут быть распознаны за время O(kn²).
To prove Dilworth's theorem for a partial order S with n elements, using Kőnig's theorem, define a bipartite graph G = (U,V,E) where U = V = S and where (u,v) is an edge in G when u < v in S. By Kőnig's theorem, there exists a matching M in G, and a set of vertices C in G, such that each edge in the graph contains at least one vertex in C and such that M and C have the same cardinality m. Let A be the set of elements of S that do not correspond to any vertex in C; then A has at least n m elements (possibly more if C contains vertices corresponding to the same element on both sides of the bipartition) and no two elements of A are comparable to each other. Let P be a family of chains formed by including x and y in the same chain whenever there is an edge (x,y) in M; then P has n m chains. Therefore, we have constructed an antichain and a partition into chains with the same cardinality. To prove Kőnig's theorem from Dilworth's theorem, for a bipartite graph G = (U,V,E), form a partial order on the vertices of G in which u < v exactly when u is in U, v is in V, and there exists an edge in E from u to v. By Dilworth's theorem, there exists an antichain A and a partition into chains P both of which have the same size. But the only nontrivial chains in the partial order are pairs of elements corresponding to the edges in the graph, so the nontrivial chains in P form a matching in the graph. The complement of A forms a vertex cover in G with the same cardinality as this matching. This connection to bipartite matching allows the width of any partial order to be computed in polynomial time. More precisely, n element partial orders of width k can be recognized in time O(kn2) .
Расширение на бесконечные частично упорядоченные множества
Теорема Дилворта для бесконечных частично упорядоченных множеств утверждает, что частично упорядоченное множество имеет конечную ширину w тогда и только тогда, когда оно может быть разбито на w цепочек. Действительно, предположим, что бесконечный частичный порядок P имеет ширину w, то есть любая антицепь содержит не более чем конечное число w элементов. Для любого подмножества S множества P, разложение на w цепочек (если оно существует) можно описать как раскраску графа несравненности множества S (графа, вершины которого – элементы S, а ребра соединяют любые два несравнимых элемента) с использованием w цветов; каждый класс цветов в правильной раскраске графа несравненности должен образовывать цепочку. По предположению о том, что P имеет ширину w, и по конечной версии теоремы Дилворта, для любого конечного подмножества S множества P граф несравненности можно раскрасить в w цветов. Следовательно, по теореме Де Брюйна — Эрдеша, сам P также имеет граф несравненности, раскрашиваемый в w цветов, и, таким образом, допускает требуемое разбиение на цепочки. Однако теорема не так просто обобщается на частично упорядоченные множества, в которых бесконечна не только кардинальность множества, но и ширина. В этом случае размер наибольшей антицепи и минимальное число цепочек, необходимых для покрытия частичного порядка, могут существенно различаться. В частности, для каждого бесконечного кардинального числа κ существует бесконечное частично упорядоченное множество ширины ℵ₀, разбиение которого на минимальное число цепочек требует κ цепочек. В работе рассматриваются аналоги теоремы Дилворта в бесконечном случае.
However, the theorem does not extend so simply to partially ordered sets in which the width, and not just the cardinality of the set, is infinite. In this case the size of the largest antichain and the minimum number of chains needed to cover the partial order may be very different from each other. In particular, for every infinite cardinal number κ there is an infinite partially ordered set of width ℵ0 whose partition into the fewest chains has κ chains
discusses analogues of Dilworth's theorem in the infinite setting.
Двойная теорема Дилворта (теорема Мирского)
Двойственная теорема Дилворта утверждает, что размер наибольшей цепи в частично упорядоченном множестве (если оно конечно) равен минимальному числу антицепей, на которые можно разбить это множество. Доказательство этой теоремы значительно проще доказательства самой теоремы Дилворта: для любого элемента x рассмотрим цепи, у которых x является максимальным элементом, и пусть N(x) обозначает размер наибольшей из этих x-максимальных цепей. Тогда каждый набор N⁻¹(i), состоящий из элементов с одинаковым значением N, является антицепью, и эти антицепи разбивают частично упорядоченное множество на число антицепей, равное размеру наибольшей цепи.
Совершенство графов сопоставимости
График сопоставимости — это ненаправленный граф, построенный из частичного порядка путём создания вершины для каждого элемента порядка и ребра, соединяющего любые два сопоставимых элемента. Следовательно, клика в графике сопоставимости соответствует цепи, а независимое множество в графике сопоставимости соответствует антицепи. Любой индуцированный подграф графа сопоставимости сам является графом сопоставимости, образованным ограничением частичного порядка на подмножество его элементов. Ненаправленный граф называется совершенным, если в каждом индуцированном подграфе хроматическое число равно размеру наибольшей клики. Каждый график сопоставимости совершенен: это, по сути, переформулировка теоремы Мирского в терминах теории графов. По теореме о совершенных графах, дополнение любого совершенного графа также является совершенным. Следовательно, дополнение любого графа сопоставимости является совершенным; это, по сути, переформулировка самой теоремы Дилворта в терминах теории графов. Таким образом, свойство дополнения совершенных графов может служить альтернативным доказательством теоремы Дилворта.
Ширина специальных частичных заказов
Булева решетка Bn — это множество степеней множества X из n элементов, по сути {1, 2, ..., n}, упорядоченное по включению, или, в обозначениях, (2[n], ⊆). Теорема Спернера утверждает, что максимальная антицепь Bn имеет размер не более
Другими словами, наибольшее семейство несравнимых подмножеств X получается путем выбора подмножеств X со средним размером. Неравенство Любелла — Ямамото — Мешалкина также относится к антицепям в множестве степеней и может быть использовано для доказательства теоремы Спернера. Если упорядочить целые числа в интервале [1, 2n] по делимости, то подинтервал [n + 1, 2n] образует антицепь с кардинальностью n. Разделить этот частичный порядок на n цепей легко: для каждого нечетного целого числа m в [1, 2n] сформировать цепь чисел вида m2i. Следовательно, по теореме Дилворта, ширина этого частичного порядка равна n.
Теорема Эрдеша — Секереша о монотонных последовательностях может быть интерпретирована как применение теоремы Дилворта к частичным порядкам размерности два. "Выпуклая размерность" антиматроида определяется как минимальное количество цепей, необходимых для определения антиматроида, и теорема Дилворта может быть использована для доказательства того, что она равна ширине связанного частичного порядка; эта связь приводит к алгоритму полиномиального времени для вычисления выпуклой размерности.
The "convex dimension" of an antimatroid is defined as the minimum number of chains needed to define the antimatroid, and Dilworth's theorem can be used to show that it equals the width of an associated partial order; this connection leads to a polynomial time algorithm for convex dimension .