Теорема Дилуорса.

Пусть ширина наибольшей антицепи в ЧУМе равна d. Тогда ЧУМ можно разбить на d цепей (каждый элемент лежит хотя бы в одной цепи).

Доказательство.

   Будем доказывать теорему по индукции по числу элементов ЧУМа.
   Заметим, что для ЧУМа из одного элемента утверждение верно.
   Пусть для всех ЧУМов, состоящих из <k элементов теорема доказана. Докажем ее и для k-элементного ЧУМа. Рассмотрим два случая.
1) Случай первый. Если есть антицепь наибольшей ширины (ширины d; обозначим эту антицепь за P), не содержащая хотя бы одного минимального элемента (обозначим его за a) и хотя бы одного максимального элемента (обозначим его за b). Введем множества M₁: {xM₁ pP p x}; M₂: {xM₂ pP  x p}. Пусть M - множество всех элементов нашего ЧУМа. Тогда M₁¹M (в M₁ не входит a); M₂¹M (в M₂ не входит b); M₁ÇM₂=M. Если это неверно, то существует элемент q, не сравнимый ни с каким элементом из P. Но тогда добавим его к P и получим антицепь ширины d+1, но P - антицепь максимальной ширины в данном ЧУМе. Противоречие, т.е. M₁ÇM₂=M. Для M₁ и M₂ по предположению индукции утверждение верно. Т.к. наибольшая антицепь в них - P, то M₁ и M₂ можно разбить на d цепей. Пусть pP, что не менее двух цепей из M₁ проходят через P. Т.к. цепей ровно d, то тогда существует sP, что через него не проходит ни одной цепи. Но M₁ разбивается на d цепей, следовательно через каждый элемент P проходит ровно одна цепь из M₁. Аналогично получаем такое же утверждение про M₂. Возьмем pP. Через него проходит по одной цепи из M₁ и M₂. Объединим эти цепи в одну новую (у этих цепей один общий конец - p). Аналогично поступим со всеми элементами P. Так мы получим разбиение на d цепей исходного ЧУМа. Переход в этом случае доказан.
2) Случай второй. Если нет такой антицепи P наибольшей ширины, которая описывалась в предыдущем случае. Тогда все антицепи максимальной ширины d либо состоят из антицепи из всех минимальных элементов, либо из антицепи из всех максимальных элементов, либо из той и другой антицепи. 2.1. Если есть только одна антицепь максимальной ширины, то, не теряя общности, будем считать, что эта антицепь - антицепь из всех минимальных элементов. Тогда отметим в этой антицепи произвольный элемент (a) и удалим его. После удаления этого элемента остается ЧУМ, причем ширина наибольшей антицепи в нем d-1. Предположим противное: пусть есть антицепь ширины d. До удаления a ее не было, т.е. были два ее элемента, которые сравнимы. Но после удаления они тоже сравнимы, т.е. и после удаления a такой цепи нет. Противоречие, т.е. ширина наибольшей антицепи d-1. По предположению индукции, ЧУМ, оставшийся после удаления a, разбивается на d-1 цепь. Тогда исходный ЧУМ разбивается на  d цепей (добавляется цепь из элемента a), т.е. разбивается на d цепей. 2.2. Если есть две несовпадающие антицепи максимальной ширины, то это антицепи из всех максимальных и из всех минимальных элементов. Тогда отметим по элементу из минимального и максимального множества элементов (a и b), чтобы они были связаны (такие есть по определению минимального и максимального элемента ЧУМа). Удалим их. Далее все обосновывается также, как и в случае 2.1. после удаления a.

В начало.
Назад.