Теорема Мирского

В математике , в области теории порядка и комбинаторики , теорема Мирского характеризует высоту любого конечного частично упорядоченного множества с точки зрения разбиения порядка на минимальное число антицепей . Он назван в честь Леона Мирского ( 1971 ) и тесно связан с теоремой Дилворта о ширинах частичных порядков, с совершенством , графов сравнимости с теоремой Галлаи-Хассе-Роя-Витавера, касающейся длиннейших путей и раскрасок в графах, а также с теорема Эрдеша –Секереша о монотонных подпоследовательностях.

Теорема

Высота частично упорядоченного набора определяется как максимальная мощность цепи , полностью упорядоченного подмножества данного частичного порядка. Например, в множестве натуральных чисел от 1 до N , упорядоченных по делимости , одна из крупнейших цепочек состоит из степеней двойки , лежащих в этом диапазоне, из чего следует, что высота этого частичного порядка равна $1+\lfloor \log _{2}N\rfloor$.

Теорема Мирского утверждает, что для каждого конечного частично упорядоченного набора высота также равна минимальному количеству антицепей (подмножеств, в которых ни одна пара элементов не упорядочена), на которые это множество может быть разделено. В таком разбиении каждые два элемента самой длинной цепи должны переходить в две разные антицепи, поэтому количество антицепей всегда больше или равно высоте; Другая формулировка теоремы Мирского состоит в том, что всегда существует разбиение, у которого количество антицепей равно высоте. Опять же, в примере натуральных чисел, упорядоченных по делимости, числа можно разбить на антицепи {1}, {2,3}, {4,5,6,7} и т. д. $1+\lfloor \log _{2}N\rfloor$ множества в этом разделе, и внутри каждого из этих наборов каждая пара чисел образует отношение меньше двух, поэтому никакие два числа в одном из этих наборов не могут быть делящимися.

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

Связанные результаты

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

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

Теорема Мирского и теорема Дилворта также связаны друг с другом через теорию совершенных графов . Неориентированный граф является совершенным , если в каждом индуцированном подграфе хроматическое число равно размеру наибольшей клики. В графе сравнимости частично упорядоченного множества клика представляет цепь, а раскраска представляет собой разбиение на антицепи, а индуцированные подграфы графов сравнимости сами по себе являются графами сравнимости, поэтому теорема Мирского утверждает, что графы сравнимости совершенны. Аналогично, теорема Дилворта утверждает, что каждый граф дополнений графа сравнимости совершенен. Теорема совершенном графе о Ловаса (1972) утверждает, что дополнения к совершенным графам всегда совершенны и могут использоваться для вывода теоремы Дилворта из теоремы Мирского и наоборот ( Golumbic 1980 ).

Теорема Могла – Хассе – Роя – Витавера.

Теорему Мирского можно переформулировать в терминах направленных ациклических графов (представляющих частично упорядоченное множество благодаря достижимости их вершин) как утверждение о том, что существует гомоморфизм графа из заданного ориентированного ациклического графа G в с k -вершинами транзитивный турнир тогда и только тогда. если не существует гомоморфизма из ( k + 1) -графа путей вершин в G . Действительно, наибольший граф путей, имеющий гомоморфизм G , дает самую длинную цепь в порядке достижимости, а множества вершин с одинаковым образом в гомоморфизме транзитивного турнира образуют разбиение на антицепи. Это утверждение обобщается на случай, когда G не является ациклическим, и является формой теоремы Галлаи–Хассе–Роя–Витавера о графов раскрасках и ориентациях ( Нешетржил и Оссона де Мендес, 2012 ).

Теорема Эрдеша – Секереша

Из теоремы Дилворта или теоремы Мирского следует, что в каждом частично упорядоченном наборе из rs + 1 элементов должна существовать цепочка из r + 1 элементов или антицепь из s + 1 элементов. Мирский (1971) использует это наблюдение, примененное к частичному порядку размерности два, для доказательства теоремы Эрдеша – Секереша о том, что в каждой последовательности из rs + 1 полностью упорядоченных элементов должна существовать монотонно возрастающая подпоследовательность из r + 1 элементов или монотонно убывающая подпоследовательность из s + 1 элементов.

Расширения

Теорема Мирского непосредственно распространяется на бесконечные частично упорядоченные множества конечной высоты. Однако связь между длиной цепи и числом антицепей в разбиении на антицепи не распространяется на бесконечные мощности: для любого бесконечного кардинального числа κ существуют частично упорядоченные множества, не имеющие бесконечной цепи и не имеющие раздел антицепей с κ или меньшим количеством антицепей ( Schmerl 2002 ).

Ссылки

• Дилворт, Роберт П. (1950), «Теорема о разложении частично упорядоченных множеств», Annals of Mathematics , 51 (1): 161–166, doi : 10.2307/1969503 , JSTOR   1969503 .
• Голумбик, Мартин Чарльз (1980), «5.7. Раскраска и другие проблемы графов сравнимости», Алгоритмическая теория графов и совершенные графы , Нью-Йорк: Academic Press, стр. 132–135, ISBN  0-12-289260-7 , МР   0562306 .
• Ловаш, Ласло (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 .
• Шмерл, Джеймс Х. (2002), «Препятствия на пути расширения теоремы Мирского», Order , 19 (2): 209–211, doi : 10.1023/A:1016541101728 , MR   1922918 , S2CID   26514679 .