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

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

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

Заявление

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

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

  1. для каждой семьи Спернер S чей союз насчитывает в общей сложности п элементы и
  2. равенство выполняется тогда и только тогда, когда S состоит из всех подмножеств п- набор элементов, имеющих размер или все, что имеет размер .

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

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

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

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

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

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

и поэтому,

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

что значит

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

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

если и только если или же заключаем, что из равенства следует, что S состоит только из наборов размеров или же Даже для п это завершает доказательство части 2.

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

Обобщения

Есть несколько обобщений теоремы Спернера для подмножеств набор всех подмножеств E.

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

А цепь это подсемейство который полностью упорядочен, т.е. (возможно, после перенумерации). В сети есть р + 1 член и длина р. An р-безцепная семья (также называемый р-семья) представляет собой семейство подмножеств E который не содержит цепочки длины р. Эрдёш (1945) доказал, что наибольший размер р-безцепная семья - это сумма р наибольшие биномиальные коэффициенты . Дело р = 1 - это теорема Спернера.

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

В комплекте из п-наборы подмножеств Eмы говорим ппара ≤ еще один, если для каждого я = 1,2,...,п. Мы называем а п-Состав E если наборы сформировать раздел E. Мешалкин (1963) доказал, что максимальный размер антицепи п-композиции самые большие п-мультиномиальный коэффициент то есть коэффициент, в котором все пя как можно более близки (т. е. отличаются не более чем на 1). Мешалкин доказал это, доказав обобщенное неравенство LYM.

Дело п = 2 - это теорема Спернера, потому что тогда а предположения сводятся к множествам будучи семьей Спернер.

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

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

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

В конечной проективной геометрии PG (d, Fq) размерности d над конечным полем порядка q, позволять - семейство всех подпространств. При частичном упорядочивании включением множества это семейство представляет собой решетку. Рота и Харпер (1971) доказал, что наибольший размер антицепи в самый большой Коэффициент Гаусса это аналог проективной геометрии, или q-аналог, теоремы Спернера.

Далее они доказали, что самый большой размер р-безцепная семья в это сумма р наибольшие гауссовы коэффициенты. Их доказательство проводится проективным аналогом неравенства LYM.

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

Бек и Заславский (2003) получил обобщение теоремы Роты – Харпера в духе Мешалкина. В PG (d, Fq), а Последовательность Мешалкина длины п это последовательность проективных подпространств таких, что никакое собственное подпространство PG (d, Fq) содержит их все, а их размеры в сумме . Теорема состоит в том, что семейство последовательностей Мешалкина длины п в PG (d, Fq), такая что подпространства, появляющиеся в позиции я последовательностей не содержат цепочки длины р для каждого не больше суммы наибольших количества

куда (в котором мы предполагаем, что ) обозначает п-Коэффициент Гаусса

и

второй элементарная симметричная функция номеров

Смотрите также

Рекомендации

внешняя ссылка