WikiDer > Теорема Спернерса - Википедия

Sperners theorem - Wikipedia

Теорема Спернера, в дискретная математика, описывает максимально возможные семьи из конечные множества ни один из которых не содержит других наборов в семействе. Это один из центральных результатов теория экстремальных множеств. Он назван в честь Эмануэль Спернер, опубликовавший его в 1928 году.

Этот результат иногда называют леммой Спернера, но имя "Лемма Спернера"также относится к несвязанному результату о раскрашивающих триангуляциях. Чтобы различать эти два результата, результат о размере семьи Спернера теперь более известен как теорема Спернера.

Заявление

А семейство наборов в котором ни одно из множеств не является строгим подмножеством другого, называется Семья Спернер, или антицепь наборов или беспорядок. Например, семья k-элементные подмножества п-элементный набор - семейство Sperner. Ни один набор в этом семействе не может содержать другие, потому что содержащий набор должен быть строго больше, чем набор, который он содержит, а в этом семействе все наборы имеют одинаковый размер. Значение k что делает этот пример максимально возможным, это п/ 2 если п четное или ближайшее целое число к п/ 2 если п странно. Для этого выбора количество наборов в семье равно ${ displaystyle { tbinom {n} { lfloor n / 2 rfloor}}}$ .

Теорема Спернера утверждает, что эти примеры являются максимально возможными семействами Спернера над п-элементное множество. Формально теорема утверждает, что

для каждой семьи Спернер S чей союз насчитывает в общей сложности п элементы ${ displaystyle | S | leq { binom {n} { lfloor n / 2 rfloor}},}$ и
равенство выполняется тогда и только тогда, когда S состоит из всех подмножеств п- набор элементов, имеющих размер ${ Displaystyle lfloor п / 2 rfloor}$ или все, что имеет размер ${ Displaystyle lceil п / 2 rceil}$ .

Частичные заказы

Теорема Спернера также может быть сформулирована в терминах ширина частичного заказа. Семейство всех подмножеств п-элементный набор (его набор мощности) возможно частично заказанный по включению множества; в этом частичном порядке два различных элемента называются несравнимыми, если ни один из них не содержит другого. Ширина частичного порядка - это наибольшее количество элементов в антицепь, набор попарно несравнимых элементов. Если перевести эту терминологию на язык множеств, антицепь - это просто семейство Спернера, а ширина частичного порядка - это максимальное количество множеств в семье Спернера. Таким образом, еще один способ сформулировать теорему Спернера состоит в том, что ширина включения заказ на силовой набор ${ Displaystyle { binom {п} { lfloor n / 2 rfloor}}}$ .

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

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

Существует множество доказательств теоремы Спернера, каждое из которых приводит к различным обобщениям (см. Anderson (1987)).

Следующее доказательство принадлежит Любель (1966). Позволять s_k обозначить количество k-установлен в S. Для всех 0 ≤ k ≤ п,

{ Displaystyle {п выбрать lfloor {п / 2} rfloor} geq {п выбрать k}}

и поэтому,

{ displaystyle {s_ {k} over {n choose lfloor {n / 2} rfloor}} leq {s_ {k} over {n choose k}}.}

С S является антицепью, мы можем просуммировать по вышеуказанному неравенству из k = От 0 до п а затем примените LYM неравенство чтобы получить

{ displaystyle sum _ {k = 0} ^ {n} {s_ {k} over {n choose lfloor {n / 2} rfloor}} leq sum _ {k = 0} ^ {n } {s_ {k} over {n choose k}} leq 1,}

что значит

{ displaystyle | S | = sum _ {k = 0} ^ {n} s_ {k} leq {n choose lfloor {n / 2} rfloor}.}

Это завершает доказательство части 1.

Чтобы иметь равенство, все неравенства в предыдущем доказательстве должны быть равенствами. С

{ Displaystyle {п выбрать lfloor {п / 2} rfloor} = {п выбрать k}}

если и только если ${ Displaystyle к = lfloor {п / 2} rfloor}$ или же ${ displaystyle lceil {п / 2} rceil,}$ заключаем, что из равенства следует, что S состоит только из наборов размеров ${ Displaystyle lfloor {п / 2} rfloor}$ или же ${ displaystyle lceil {n / 2} rceil.}$ Даже для п это завершает доказательство части 2.

Для нечетных п предстоит еще работа, которую мы здесь опускаем, потому что она сложна. См. Anderson (1987), стр. 3–4.

Обобщения

Есть несколько обобщений теоремы Спернера для подмножеств ${ displaystyle { mathcal {P}} (E),}$ набор всех подмножеств E.

Без длинных цепей

А цепь это подсемейство ${ displaystyle {S_ {0}, S_ {1}, dots, S_ {r} } substeq { mathcal {P}} (E)}$ который полностью упорядочен, т.е. ${ Displaystyle S_ {0} подмножество S_ {1} подмножество точки подмножество S_ {r}}$ (возможно, после перенумерации). В сети есть р + 1 член и длина р. An р-безцепная семья (также называемый р-семья) представляет собой семейство подмножеств E который не содержит цепочки длины р. Эрдёш (1945) доказал, что наибольший размер р-безцепная семья - это сумма р наибольшие биномиальные коэффициенты ${ Displaystyle { binom {п} {я}}}$ . Дело р = 1 - это теорема Спернера.

п-композиции набора

В комплекте ${ Displaystyle { mathcal {P}} (E) ^ {p}}$ из п-наборы подмножеств Eмы говорим ппара ${ Displaystyle (S_ {1}, точки, S_ {p})}$ ≤ еще один, ${ displaystyle (T_ {1}, dots, T_ {p}),}$ если ${ displaystyle S_ {i} substeq T_ {i}}$ для каждого я = 1,2,...,п. Мы называем ${ displaystyle (S_ {1}, dots, S_ {p})}$ а п-Состав E если наборы ${ Displaystyle S_ {1}, точки, S_ {p}}$ сформировать раздел E. Мешалкин (1963) доказал, что максимальный размер антицепи п-композиции самые большие п-мультиномиальный коэффициент ${ Displaystyle { binom {n} {n_ {1} n_ {2} dots n_ {p}}},}$ то есть коэффициент, в котором все п_я как можно более близки (т. е. отличаются не более чем на 1). Мешалкин доказал это, доказав обобщенное неравенство LYM.

Дело п = 2 - это теорема Спернера, потому что тогда ${ Displaystyle S_ {2} = E setminus S_ {1}}$ а предположения сводятся к множествам ${ displaystyle S_ {1}}$ будучи семьей Спернер.

Нет длинных цепей в п-композиции набора

Бек и Заславский (2002) объединил теоремы Эрдеша и Мешалкина, адаптировав доказательство Мешалкиным его обобщенного неравенства LYM. Они показали, что самый большой размер семьи п-композиции такие, что множества в я-я позиция п-кортежи, игнорируя дублирование, являются р-без цепи, для каждого ${ Displaystyle я = 1,2, точки, п-1}$ (но не обязательно для я = п), не больше суммы ${ displaystyle r ^ {p-1}}$ самый большой п-мультиномиальные коэффициенты.

Аналог проективной геометрии

В конечной проективной геометрии PG (d, F_q) размерности d над конечным полем порядка q, позволять ${ displaystyle { mathcal {L}} (p, F_ {q})}$ - семейство всех подпространств. При частичном упорядочивании включением множества это семейство представляет собой решетку. Рота и Харпер (1971) доказал, что наибольший размер антицепи в ${ displaystyle { mathcal {L}} (p, F_ {q})}$ самый большой Коэффициент Гаусса ${ Displaystyle { begin {bmatrix} d + 1 k end {bmatrix}};}$ это аналог проективной геометрии, или q-аналог, теоремы Спернера.

Далее они доказали, что самый большой размер р-безцепная семья в ${ displaystyle { mathcal {L}} (p, F_ {q})}$ это сумма р наибольшие гауссовы коэффициенты. Их доказательство проводится проективным аналогом неравенства LYM.

Нет длинных цепей в п-композиции проективного пространства

Бек и Заславский (2003) получил обобщение теоремы Роты – Харпера в духе Мешалкина. В PG (d, F_q), а Последовательность Мешалкина длины п это последовательность ${ displaystyle (A_ {1}, ldots, A_ {p})}$ проективных подпространств таких, что никакое собственное подпространство PG (d, F_q) содержит их все, а их размеры в сумме ${ displaystyle d-p + 1}$ . Теорема состоит в том, что семейство последовательностей Мешалкина длины п в PG (d, F_q), такая что подпространства, появляющиеся в позиции я последовательностей не содержат цепочки длины р для каждого ${ Displaystyle я = 1,2, точки, п-1,}$ не больше суммы наибольших ${ displaystyle r ^ {p-1}}$ количества

{ displaystyle { begin {bmatrix} d + 1 n_ {1} n_ {2} dots n_ {p} end {bmatrix}} q ^ {s_ {2} (n_ {1}, ldots, n_ {p})},}

куда ${ displaystyle { begin {bmatrix} d + 1 n_ {1} n_ {2} dots n_ {p} end {bmatrix}}}$ (в котором мы предполагаем, что ${ displaystyle d + 1 = n_ {1} + cdots + n_ {p}}$ ) обозначает п-Коэффициент Гаусса