Математика · объяснение и практика

Теорема Дилворта: сколько цепей нужно частичному порядку

Связываем наибольшую антицепь с наименьшим разбиением на цепи и доказываем равенство через два экземпляра каждого элемента и паросочетание.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

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

Антицепь даёт нижнюю границу числу цепей

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

Ширина порядка — максимальный размер антицепи, а не число максимальных элементов и не длина самой длинной цепи. У делителей числа 12 по делимости максимальный элемент всего один — 12, однако 4 и 6 несравнимы. Таким образом, максимальные элементы не измеряют требуемое число вертикальных цепочек.

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

Два экземпляра элемента превращают склейку в паросочетание

Создадим левый и правый экземпляры каждого из n элементов. Проведём ребро от левой копии x к правой копии y для каждого строгого сравнения x<y. Нужны все такие сравнения, в том числе восстанавливаемые транзитивностью, а не только соседние линии диаграммы Хассе.

Паросочетание размера m задаёт m связок x→y. У исходного элемента не больше одного предшественника и одного продолжения. Циклов нет, поскольку вдоль связок порядок строго возрастает. Поэтому получаются непересекающиеся пути, то есть цепи, и их число n−m: каждая связка уменьшает число отдельных компонентов на единицу.

Обратно, в каждой цепи разбиения соединим соседей. Для k цепей получается n−k связок, образующих паросочетание копий. Значит, наибольшее паросочетание даёт наименьшее число цепей. Осталось связать этот минимум с антицепью, а не только с графовой задачей.

Пример

Разбейте делители 12 на минимальное число цепей по делимости и докажите минимальность.

Набор {1,2,3,4,6,12} разбивается на цепи 1|2|4|12 и 3|6. Множество {4,6} — антицепь: ни 4 не делит 6, ни 6 не делит 4. Поэтому одна цепь невозможна, а две уже построены. То, что 12 является единственным максимальным элементом, не уменьшает ширину до единицы.

Вершинное покрытие даёт встречную антицепь

По теореме Кёнига у наибольшего паросочетания размера m есть вершинное покрытие размера m. Соберём исходные элементы, у которых ни левая, ни правая копия не входит в покрытие. Удаление m копий может исключить не больше m исходных элементов, так что собранных осталось хотя бы n−m.

Два собранных элемента не могут быть сравнимы. Иначе соответствующее ребро между их копиями не имело бы конца в покрытии. Получена антицепь размера хотя бы n−m. Но уже построенное разбиение на n−m цепей не позволяет антицепи быть больше. Обе оценки совпадают и завершают доказательство.

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

От чтения к действию

А теперь — вы

В порядке a,b<x<c,d, где a и b несравнимы, а c и d несравнимы, возможно ли разбиение на две цепи, хотя между b и d нет непосредственной линии Хассе?

Частые вопросы

Цепь обязана идти только по соседним рёбрам диаграммы Хассе?

Нет. Между соседями выбранной цепи могут находиться элементы, включённые в другие цепи. Достаточно сравнимости.

Теорема говорит о длине наибольшей цепи?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться