В математике , в области теории порядка и комбинаторики , теорема Дилворта характеризует ширину любого конечного частично упорядоченного множества в терминах разбиения порядка на минимальное количество цепочек . Он назван в честь математика Роберта П. Дилворта ( 1950 ).
Антицепь в частично упорядоченное множество представляет собой набор элементов никакие два из которых не сопоставимы друг с другом, а также цепь представляет собой набор элементов каждые два из которых являются сопоставимыми. Цепное разложение - это разбиение элементов порядка на непересекающиеся цепи. Теорема Дилворта утверждает, что в любом конечном частично упорядоченном множестве наибольшая антицепь имеет тот же размер, что и наименьшее разложение цепи. Здесь размер антицепи - это количество ее элементов, а размер разложения цепочки - это количество цепочек. Ширина частичного порядка определяется как общий размер антицепи и цепной декомпозиции.
Версия теоремы для бесконечных частично упорядоченных множеств гласит, что, когда существует разбиение на конечное число цепочек или когда существует конечная верхняя граница размера антицепи, размеры наибольшей антицепи и наименьшего разложения цепи снова равны.
Индуктивное доказательство
Следующее доказательство индукцией по размеру частично упорядоченного множества основан на исследовании Гэлвина ( 1994 ).
Позволять - конечное частично упорядоченное множество. Теорема выполняется тривиально, еслипустой. Итак, предположим, что имеет хотя бы один элемент, и пусть быть максимальным элементом .
По индукции предполагаем, что для некоторого целого числа частично упорядоченный набор может быть покрыт непересекающиеся цепи и имеет как минимум одну антицепь размера . Четко, для . Для, позволять быть максимальным элементом в что принадлежит антицепи размера в , и установите . Мы утверждаем, чтоэто антицепь. Позволять быть антицепью размера это содержит . Зафиксируйте произвольные различные индексы а также . потом. Позволять. потом, по определению . Это означает, что, поскольку . Меняя ролями а также в этом аргументе мы также имеем . Это подтверждает, что это антицепь.
Теперь вернемся к . Предположим сначала, что для некоторых . Позволять быть цепью . Тогда по выбору, не имеет антицепи размера . Тогда индукция означает, что может быть покрыт непересекающиеся цепи, поскольку это антицепь размера в . Таким образом, может быть покрыт непересекающиеся цепи, если требуется. Далее, если для каждого , тогда это антицепь размера в (поскольку максимально в ). Сейчас может быть покрыт цепи , завершая доказательство.
Доказательство с помощью теоремы Кёнига.
Как и ряд других результатов в комбинаторике, теорема Дилворта эквивалентна теореме Кёнига о паросочетании двудольных графов и ряду других связанных теорем, включая теорему Холла о браке ( Фулкерсон, 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 содержит вершины, соответствующие одному и тому же элементу по обе стороны от двудольного разделения), и никакие два элемента 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 2 ) ( Felsner, Raghavan & Spinrad 2003 ).
Расширение до бесконечных частично упорядоченных множеств
Теорема Дилворта для бесконечных частично упорядоченных множеств утверждает, что частично упорядоченное множество имеет конечную ширину w тогда и только тогда, когда оно может быть разбито на w цепочек. В самом деле , предположим, что бесконечный частичный порядок P имеет ширину w , что означает, что в любой антицепи имеется не более конечного числа w элементов. Для любого подмножества S из Р , разложение на ш цепи (если он существует) может быть описан как окраски на несравнимости графа из S (граф , который имеет элементы S в качестве вершин, с краем между каждыми двумя несравнимыми элементами) используя w цветов; каждый цветовой класс в правильной раскраске графа несравнимости должен быть цепью. По предположению, что P имеет ширину w , и по конечной версии теоремы Дилворта каждое конечное подмножество S в P имеет w- раскрашиваемый граф несравнимости. Следовательно, согласно теореме Де Брёйна – Эрдеша , сама P также имеет w- раскрашиваемый граф несравнимости и, таким образом, имеет желаемое разбиение на цепи ( Harzheim 2005 ).
Однако теорема не распространяется так просто на частично упорядоченные множества, в которых ширина, а не только мощность множества, бесконечна. В этом случае размер наибольшей антицепи и минимальное количество цепочек, необходимых для покрытия частичного порядка, могут сильно отличаться друг от друга. В частности, для каждого бесконечного кардинального числа κ существует бесконечное частично упорядоченное множество шириной ℵ 0 , разбиение которого на наименьшее количество цепочек содержит κ цепей ( Harzheim 2005 ).
Perles (1963) обсуждает аналоги теоремы Дилворта в бесконечном контексте.
Двойственная теорема Дилворта (теорема Мирского)
Двойственная теорема Дилворта гласит, что размер наибольшей цепи в частичном порядке (если он конечен) равен наименьшему количеству антицепей, на которые может быть разделен порядок ( Мирский, 1971 ). Доказательство этого намного проще, чем доказательство самой теоремы Дилворта: для любого элемента x рассмотрим цепи, у которых x является их наибольшим элементом, и пусть N ( x ) обозначает размер наибольшей из этих x -максимальных цепей. Тогда каждое множество N −1 ( i ), состоящее из элементов, имеющих равные значения N , является антицепью, и эти антицепи разделяют частичный порядок на количество антицепей, равное размеру наибольшей цепи.
Совершенство графиков сопоставимости
Сопоставимость график представляет собой неориентированный граф образован из частичного порядка, создавая вершину для каждого элемента порядка, и ребро , соединяющее любых две сопоставимых элементов. Таким образом, клика в графе сопоставимости соответствует цепи, а независимый набор в графе сопоставимости соответствует антицепи. Любой индуцированный подграф графа сопоставимости сам по себе является графом сопоставимости, сформированным из ограничения частичного порядка на подмножество его элементов.
Ненаправленный граф идеален, если в каждом индуцированном подграфе хроматическое число равно размеру наибольшей клики. Каждый граф сопоставимости совершенен: по сути, это просто теорема Мирского, сформулированная в терминах теории графов ( Berge & Chvátal 1984 ). По идеальной теореме графа из Lovász (1972) , то дополнение любого идеального графика также идеально. Следовательно, дополнение любого графа сопоставимости идеально; по сути, это просто сама теорема Дилворта, переформулированная в терминах теории графов ( Berge & Chvátal 1984 ). Таким образом, свойство дополняемости совершенных графов может предоставить альтернативное доказательство теоремы Дилворта.
Ширина специальных частичных заказов
Булева решетка В п есть множество мощности из п - элементного множества X -essentially {1, 2, ..., п } -ordered путем включения или, notationally, (2 [ п ] , ⊆). Теорема Спернера утверждает, что максимальная антицепь B n имеет размер не более
Другими словами, наибольшее семейство несравнимых подмножеств X получается путем выбора подмножеств X, которые имеют средний размер. Неравенство Lubell-Ямамото Мешалкин также относится антицепи в наборе мощности и может быть использовано для доказательства теоремы Шпернера.
Если мы упорядочим целые числа в интервале [1, 2 n ] по делимости , то подынтервал [ n + 1, 2 n ] образует антицепь с мощностью n . Разделить этот частичный порядок на n цепочек легко: для каждого нечетного целого числа m в [1,2 n ] сформируйте цепочку чисел вида m 2 i . Следовательно, по теореме Дилворта ширина этого частичного порядка равна n .
Теорема Эрдеша – Секереса о монотонных подпоследовательностях может быть интерпретирована как приложение теоремы Дилворта к частичным порядкам размерности два ( Steele, 1995 ).
«Выпуклая размерность» антиматроида определяется как минимальное количество цепей, необходимых для определения антиматроида, и теорема Дилворта может использоваться, чтобы показать, что она равна ширине соответствующего частичного порядка; эта связь приводит к полиномиальному алгоритму времени для выпуклой размерности ( Edelman & Saks 1988 ).
Рекомендации
- Берже, Клод ; Chvátal, Václav (1984), Topics on Perfect Graphs , Annals of Discrete Mathematics, 21 , Elsevier, p. viii, ISBN 978-0-444-86587-8
- Дилворт, Роберт П. (1950), "Разложение теорема для частично упорядоченных множеств", Анналы математики , 51 (1): 161-166, DOI : 10.2307 / 1969503 , JSTOR 1969503.
- Эдельман, Пол Х .; Сакс, Michael E. (1988), "Комбинаторное представление и выпуклая размерность выпуклых геометрий", заказ , 5 (1): 23-32, DOI : 10.1007 / BF00143895 , S2CID 119826035.
- Фельснер, Стефан; Рагхаван, Виджай; Спинрад, Джереми (2003), "Алгоритмы распознавания для порядков малой ширины и графиков небольшого числа Dilworth" , заказ , 20 (4): 351-364 (2004), DOI : 10,1023 / B: ORDE.0000034609.99940.fb , MR 2079151 , S2CID 1363140.
- Фулкерсон, DR (1956), "Замечание о теореме разложения Дилуорса для частично упорядоченных множеств", Труды Американского математического общества , 7 (4): 701-702, DOI : 10,2307 / 2033375 , JSTOR 2033375.
- Гальвин, Фред (1994), "Доказательство теоремы разложения цепи Дилуорса", Американский Математический Месячный , 101 (4): 352-353, DOI : 10,2307 / 2975628 , JSTOR 2975628 , MR 1270960.
- Грин, Кертис ; Клейтман, Дэниел Дж. (1976), "Структура Спернера-семейства », J. Combin. Теория Сер. A , 20 (1): 41–68, DOI : 10.1016 / 0097-3165 (76) 90077-7.
- Харцхейм, Эгберт (2005), Упорядоченные множества , Успехи в математике (Springer), 7 , Нью-Йорк: Спрингер, теорема 5.6, с. 60, ISBN 0-387-24219-8, MR 2127991.
- Ловас, Ласло (1972), «Нормальные гиперграфы и гипотеза идеального графа», Дискретная математика , 2 (3): 253–267, DOI : 10.1016 / 0012-365X (72) 90006-4.
- Мирский, Leon (1971), "Двойственная теоремы разложения Дилуорса", American Mathematical Monthly , 78 (8): 876-877, DOI : 10,2307 / 2316481 , JSTOR 2316481.
- Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Теорема 3.13», Разреженность: графы, структуры и алгоритмы , алгоритмы и комбинаторика, 28 , Гейдельберг: Спрингер, стр. 42, DOI : 10.1007 / 978-3-642-27875-4 , ЛВП : 10338.dmlcz / 143192 , ISBN 978-3-642-27874-7, MR 2920058.
- Perles, Миха А. (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) 2011-07-20
- Felsner, S .; Рагхаван В. и Спинрад Дж. (1999), Алгоритмы распознавания порядков малой ширины и графов малого числа Дилворта
- Вайсштейн, Эрик В. «Лемма Дилворта» . MathWorld .