Теорема Мирского - Mirsky's theorem

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

Теорема

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

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

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

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

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

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

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

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

Теорема Мирского может быть переформулирована в терминах ориентированных ациклических графов (представляющих частично упорядоченное множество по достижимости их вершин) как утверждение, что существует гомоморфизм графов из заданного ориентированного ациклического графа G в транзитивный турнир с k- вершинами тогда и только тогда. если не существует гомоморфизм из ( K + 1) -vertex пути графа к G . В самом деле, наибольший граф путей, гомоморфный G, дает самую длинную цепочку в порядке достижимости, а множества вершин с одним и тем же образом в гомоморфизме транзитивного турнира образуют разбиение на антицепи. Это утверждение обобщается на случай , что G не ациклические и является формой теоремы Галлаи-Хассе-Рой-Vitaver на графах раскрасок и ориентации ( Nešetřil и Ossona де Мендес 2012 ).

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

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

Расширения

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

Languages

In other projects