Рубрики

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

Пусть S — конечное частично упорядоченное множество . Размер максимальной антицепи равен размеру минимальной цепной оболочки S. Это называется теорема Дилворта . Он назван в честь математика Роберта П. Дилворта (1950).

Ширина конечного частично упорядоченного множества S — это максимальный размер антицепи в S. Другими словами, ширина конечного частично упорядоченного множества S — это минимальное количество цепочек, необходимых для покрытия S, т. Е. Минимальное количество цепочек, таких что любой элемент S находится хотя бы в одной из цепей.

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

Наглядные примеры:

Let S be the set of divisors of 30, with divisibility as the partial order. 
Then the following chains cover S : 
{1, 2, 6, 30}, {3, 15}, {5, 10}

And {2, 3, 5} is an antichain of length 3. 
It is not immediately obvious, but the chain cover is minimal (though not unique), 
and the antichain is maximal (though not unique). 

So both definitions of width give 3 for this partially ordered set. 

Доказательство теоремы Дилворта:
Самым простым доказательством является индукция по размеру набора. Пусть d будет размером наибольшей антицепи S. Доказательство покажет, что S может быть покрыто d цепями. Базовый случай тривиален. Итак, предположим, что результат был доказан для всех множеств, меньших S.

Во-первых, если нет двух сравнимых с S элементов, то сам S является антицепью и может быть покрыт d = | S | цепочки каждой длины 1, так что результат верен. В противном случае, пусть m — минимальный элемент (m <= z для всех сопоставимых z), а M — максимальный элемент (z <= M для всех сопоставимых z). Пусть T = S — {m, M}. Если самый большой антицепь в T имеет размер <= d — 1, то T может быть покрыт цепями d — 1, и поэтому S может быть покрыт этими цепочками плюс цепь {m, M}, и результат будет доказан для S ,

Теперь предположим, что самая большая антицепь в T имеет размер d (она не может быть больше, потому что T является подмножеством S). Назовите это антицепью А.

Идея остальной части доказательства такова: представьте диаграмму Хассе для S, где самая большая антицепь состоит из горизонтальной полосы. Возьмите все, что находится под полосой, и все, что находится над полосой, используйте индукцию, чтобы покрыть их цепями, а затем соедините их вместе, соединяя их поперек полосы.

То есть построить два набора

S + = {x принадлежит S: x> = a для некоторого a принадлежит A}
S = {x принадлежит S: x <= a для некоторых a принадлежит A}

Тогда S + US должно быть всем S, потому что если бы не было, то A не было бы максимальной антицепью в S. И S + US = A, потому что если x находится на пересечении, то a <= x < = b для некоторых элементов a, b принадлежит A, поэтому a и b сравнимы по транзитивности, поэтому единственная возможность состоит в том, что a = b и они оба равны x.

Поскольку m и M не находятся в A, это должно быть в том случае, если и m не принадлежит S +, а m не принадлежит S-, поэтому оба набора), и они строго меньше S. Индуктивная гипотеза применима к обоим S и S + , поэтому они оба покрыты d цепями, каждая из которых должна содержать ровно один элемент A. Назовите их C a и C a + . Теперь мы можем сшить эти покрытия, чтобы получить покрытие всех S цепями C a U {a} UC a + . Это покрытие имеет d цепочки, поэтому результат следует по индукции.

Код для иллюстрации приведенного выше примера:
Классический алгоритм O (N lg N) для наибольшей возрастающей подпоследовательности (LIS) можно рассматривать как приложение теоремы Дилворта. Смотрите здесь

Рекомендации: Youtube видео

Рекомендуемые посты:

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

0.00 (0%) 0 votes