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

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
В конечном частично упорядоченном множестве наименьшее число цепей, на которые можно разбить все элементы, равно наибольшему размеру антицепи. Цепь состоит из попарно сравнимых элементов, антицепь — из попарно несравнимых. Речь идёт о разбиении без пропусков и повторного использования элементов.
Антицепь даёт нижнюю границу числу цепей
Одна цепь может содержать не больше одного элемента заданной антицепи. Поэтому антицепь размера 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 цепей не позволяет антицепи быть больше. Обе оценки совпадают и завершают доказательство.
Теорема утверждает существование оптимального разбиения, но произвольно выбранная длинная цепь не обязательно входит в удобное оптимальное решение. Также разные минимальные разбиения могут выглядеть по-разному. Проверять конкретный ответ удобно двумя свидетельствами: самим разбиением и антицепью того же размера.
От чтения к действию
А теперь — вы
Частые вопросы
Цепь обязана идти только по соседним рёбрам диаграммы Хассе?
Нет. Между соседями выбранной цепи могут находиться элементы, включённые в другие цепи. Достаточно сравнимости.
Теорема говорит о длине наибольшей цепи?
Нет. Она связывает ширину, то есть размер антицепи, с числом цепей в разбиении всего порядка.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему в частичном порядке не всякая пара сравнима
Как распознавать частичный порядок, различать несравнимые элементы, максимальный и наибольший объект и читать порядок по включению или делимости.
Открыть темуПаросочетание: как чередующийся путь увеличивает число пар
Увеличивающий путь в двудольном паросочетании: перестановка занятых назначений вместо жадного отказа свободной вершине.
Открыть тему