Теорема Дилворта

«Цепная декомпозиция» перенаправляется сюда. Информацию о декомпозиции пути см. в разделе « Разложение тяжелого пути» .

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

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

Заявление

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

Индуктивное доказательство

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

Позволять $P$ — конечное частично упорядоченное множество. Теорема тривиально справедлива, если $P$ пусто. Итак, предположим, что $P$ имеет хотя бы один элемент, и пусть $a$ быть максимальным элементом $P$.

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

Теперь мы возвращаемся к $P$. Предположим сначала, что $a\geq x_{i}$ для некоторых $i\in \{1,2,\dots ,k\}$. Позволять $K$ быть цепью $\{a\}\cup \{z\in C_{i}:z\leq x_{i}\}$. Тогда по выбору $x_{i}$, $P\setminus K$ не имеет антицепи размера $k$. Тогда индукция означает, что $P\setminus K$ может быть покрыто $k-1$ непересекающиеся цепи, поскольку $A\setminus \{x_{i}\}$ представляет собой антицепь размера $k-1$ в $P\setminus K$. Таким образом, $P$ может быть покрыто $k$ непересекающиеся цепи, как требуется. Далее, если $a\not \geq x_{i}$ для каждого $i\in \{1,2,\dots ,k\}$, затем $A\cup \{a\}$ представляет собой антицепь размера $k+1$ в $P$ (с $a$ является максимальным в $P$). Сейчас $P$ может быть охвачено $k+1$ цепи $\{a\},C_{1},C_{2},\dots ,C_{k}$, завершая доказательство.

Доказательство с помощью теоремы Кенига.

Доказательство теоремы Дилворта с помощью теоремы Кенига: построение двудольного графа из частичного порядка и разбиение на цепи в соответствии с паросочетанием.

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

Чтобы доказать теорему Дилворта для частичного порядка 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 есть ребро ( 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 той же мощности, что и это паросочетание.

Эта связь с двусторонним сопоставлением позволяет вычислять ширину любого частичного порядка за полиномиальное время . Точнее, n -элементные частичные порядки ширины k можно распознать за время O ( kn ² ).

Расширение до бесконечных частично упорядоченных множеств.

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

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

Перлз (1963) обсуждает аналоги теоремы Дилворта в бесконечной ситуации.

Двойственная теорема Дилворта (теорема Мирского)

Основная статья: теорема Мирского

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

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

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

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

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

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

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

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

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

Теорему Эрдеша-Секереша о монотонных подпоследовательностях можно интерпретировать как применение теоремы Дилворта к частичным порядкам размерности два.

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

Ссылки

• Берже, Клод ; Хватал, Вацлав (1984), Темы о совершенных графах , Анналы дискретной математики, том. 21, Эльзевир, с. VIII , ISBN  978-0-444-86587-8
• Дилворт, Роберт П. (1950), «Теорема о разложении частично упорядоченных множеств», Annals of Mathematics , 51 (1): 161–166, doi : 10.2307/1969503 , JSTOR   1969503 .
• Эдельман, Пол Х.; Сакс, Майкл Э. (1988), «Комбинаторное представление и выпуклая размерность выпуклых геометрий», Order , 5 (1): 23–32, doi : 10.1007/BF00143895 , S2CID   119826035 .
• Фельснер, Стефан; Рагхаван, Виджай; Спинрад, Джереми (2003), «Алгоритмы распознавания порядков малой ширины и графов малого числа Дилворта» , Order , 20 (4): 351–364 (2004), doi : 10.1023/B:ORDE.0000034609.99940.fb , MR   2079151 , S2CID   1363140 .
• Фулкерсон, Д.Р. (1956), «Примечание к теореме Дилворта о разложении частично упорядоченных множеств», Proceedings of the American Mathematical Society , 7 (4): 701–702, doi : 10.2307/2033375 , JSTOR   2033375 .
• Гэлвин, Фред (1994), «Доказательство теоремы о разложении цепи Дилворта», The American Mathematical Monthly , 101 (4): 352–353, doi : 10.2307/2975628 , JSTOR   2975628 , MR   1270960 .
• Грин, Кертис ; Клейтман, Дэниел Дж. (1976), «Структура Спернера $k$-семейства», Журнал комбинаторной теории, серия A , 20 (1): 41–68, doi : 10.1016/0097-3165(76)90077-7 .
• Харцхайм, Эгберт (2005), Упорядоченные множества , Успехи в математике (Springer), том. 7, Нью-Йорк: Спрингер, Теорема 5.6, с. 60, ISBN  0-387-24219-8 , МР   2127991 .
• Ловаш, Ласло (1972), «Нормальные гиперграфы и гипотеза об идеальном графе», Discrete Mathematics , 2 (3): 253–267, doi : 10.1016/0012-365X(72)90006-4 .
• Мирский, Леон (1971), «Двойная теорема Дилворта о разложении», American Mathematical Monthly , 78 (8): 876–877, doi : 10.2307/2316481 , JSTOR   2316481 .
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Теорема 3.13», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Гейдельберг: Springer, с. 42, номер домена : 10.1007/978-3-642-27875-4 , ISBN  978-3-642-27874-7 , МР   2920058 .
• Перлес, Миха А. (1963), «О теореме Дилворта в бесконечном случае», Израильский журнал математики , 1 (2): 108–109, doi : 10.1007/BF02759806 , MR   0168497 , S2CID   120943065 .
• Стил, Дж. Майкл (1995), «Вариации на тему монотонной последовательности Эрдеша и Секереса», у Олдоса, Дэвида ; Диаконис, Персия ; Спенсер, Джоэл ; и др. (ред.), Дискретная вероятность и алгоритмы (PDF) , Тома IMA по математике и ее приложениям, том. 72, Springer-Verlag, стр. 111–131 .

Внешние ссылки

• Эквивалентность семи основных теорем комбинаторики
• «Двойная теорема Дилворта» , PlanetMath , заархивировано из оригинала 14 июля 2007 г.
• Бабай, Ласло (2005), Конспекты лекций по комбинаторике и теории вероятностей, Лекция 10: Совершенные графы (PDF) , заархивировано из оригинала (PDF) 20 июля 2011 г.
• Фельснер, С.; Рагхаван В. и Спинрад Дж. (1999), Алгоритмы распознавания порядков малой ширины и графов малого числа Дилворта
• Вайсштейн, Эрик В. «Лемма Дилворта» . Математический мир .