WikiDer > Теорема Дилуортса - Википедия

Dilworths theorem - Wikipedia

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

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

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

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

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

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

По индукции предполагаем, что для некоторого целого числа частично упорядоченный набор может быть покрыт непересекающиеся цепи и имеет как минимум одну антицепь размера . Четко, за . За , позволять быть максимальным элементом в что принадлежит антицепи размера в , и установите . Мы утверждаем, что это антицепь. Позволять быть антицепью размера который содержит . Зафиксируйте произвольные различные индексы и . потом . Позволять . потом , по определению . Отсюда следует, что , поскольку . Меняя ролями и в этом аргументе мы также имеем . Это подтверждает, что это антицепь.

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

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

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

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

Чтобы доказать теорему Дилворта для частичного порядка S с п элементы, используя теорему Кёнига, определяют двудольный граф грамм = (U,V,E) куда U = V = S и где (ты,v) является ребром в грамм когда ты < v в S. По теореме Кёнига существует паросочетание M в грамм, и набор вершин C в грамм, такое, что каждое ребро графа содержит хотя бы одну вершину из C и такой, что M и C иметь одинаковую мощность м. Позволять А быть набором элементов S которые не соответствуют ни одной вершине в C; тогда А имеет по крайней мере п - м элементы (возможно, больше, если C содержит вершины, соответствующие одному и тому же элементу по обе стороны от двудольного деления), и нет двух элементов из А сопоставимы друг с другом. Позволять п быть семьей цепей, образованных включением Икс и у в той же цепи всякий раз, когда есть ребро (Икс,у) в M; тогда п имеет п - м цепи. Таким образом, мы построили антицепь и разбиение на цепочки одинаковой мощности.

Чтобы доказать теорему Кёнига из теоремы Дилворта, для двудольного графа грамм = (U,V,E), образуют частичный порядок в вершинах грамм в котором ты < v именно когда ты в U, v в V, и в E из ты к v. По теореме Дилворта существует антицепь А и разбиение на цепочки п оба имеют одинаковый размер. Но единственные нетривиальные цепи в частичном порядке - это пары элементов, соответствующие ребрам в графе, поэтому нетривиальные цепи в п сформировать соответствие на графике. Дополнение А образует вершинное покрытие в грамм с той же мощностью, что и это сопоставление.

Эта связь с двудольным соответствием позволяет вычислить ширину любого частичного порядка в полиномиальное время. Точнее, п-элементы частичного порядка ширины k можно распознать вовремя О(кн2) (Фельснер, Рагхаван и Спинрад 2003).

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

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

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

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

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

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

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

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

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

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

В Логическая решетка Bп это набор мощности из п-элементный набор Икс—Обязательно {1, 2,…, п}-заказан включение или, условно, (2[п], ⊆). Теорема Спернера заявляет, что максимальная антицепь Bп имеет размер не больше

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

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

В Теорема Эрдеша – Секереса на монотонных подпоследовательностях можно интерпретировать как приложение теоремы Дилворта к частичным порядкам размер заказа два (Стил 1995).

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

Рекомендации

внешняя ссылка