Теорема Спернерса - Sperners theorem - Wikipedia

По поводу теоремы о симплексах см. Лемма Спернера.

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

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

Заявление

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

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

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

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

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

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

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

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

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

${\displaystyle {n \choose \lfloor {n/2}\rfloor }\geq {n \choose 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 {n \choose \lfloor {n/2}\rfloor }={n \choose k}}$

если и только если ${\displaystyle k=\lfloor {n/2}\rfloor }$ или же ${\displaystyle \lceil {n/2}\rceil ,}$ заключаем, что из равенства следует, что S состоит только из наборов размеров ${\displaystyle \lfloor {n/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}\}\subseteq {\mathcal {P}}(E)}$ который полностью упорядочен, т.е. ${\displaystyle S_{0}\subset S_{1}\subset \dots \subset S_{r}}$ (возможно, после перенумерации). В сети есть р + 1 член и длина р. An р-безцепная семья (также называемый р-семья) представляет собой семейство подмножеств E который не содержит цепочки длины р. Эрдёш (1945) доказал, что наибольший размер р-безцепная семья - это сумма р наибольшие биномиальные коэффициенты ${\displaystyle {\binom {n}{i}}}$. Дело р = 1 - это теорема Спернера.

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

В комплекте ${\displaystyle {\mathcal {P}}(E)^{p}}$ из п-наборы подмножеств Eмы говорим ппара ${\displaystyle (S_{1},\dots ,S_{p})}$ ≤ еще один, ${\displaystyle (T_{1},\dots ,T_{p}),}$ если ${\displaystyle S_{i}\subseteq T_{i}}$ для каждого я = 1,2,...,п. Мы называем ${\displaystyle (S_{1},\dots ,S_{p})}$ а п-Состав E если наборы ${\displaystyle S_{1},\dots ,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 i=1,2,\dots ,p-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 i=1,2,\dots ,p-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}}$) обозначает п-Коэффициент Гаусса

${\displaystyle {\begin{bmatrix}d+1\\n_{1}\end{bmatrix}}{\begin{bmatrix}d+1-n_{1}\\n_{2}\end{bmatrix}}\cdots {\begin{bmatrix}d+1-(n_{1}+\cdots +n_{p-1})\\n_{p}\end{bmatrix}}}$

и

${\displaystyle s_{2}(n_{1},\ldots ,n_{p}):=n_{1}n_{2}+n_{1}n_{3}+n_{2}n_{3}+n_{1}n_{4}+\cdots +n_{p-1}n_{p},}$

второй элементарная симметричная функция номеров ${\displaystyle n_{1},n_{2},\dots ,n_{p}.}$

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

• Математический портал

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

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

• Андерсон, Ян (1987), Комбинаторика конечных множеств, Oxford University Press.
• Бек, Матиас; Заславский, Томас (2002), "Более короткое, простое и более сильное доказательство границ Мешалкина-Хохберга-Хирша на покомпонентных антицепях", Журнал комбинаторной теории, серия A, 100 (1): 196–199, arXiv:математика / 0112068, Дои:10.1006 / jcta.2002.3295, МИСТЕР  1932078.
• Бек, Матиас; Заславский, Томас (2003), «Теорема Мешалкина для проективных геометрий», Журнал комбинаторной теории, серия A, 102 (2): 433–441, arXiv:математика / 0112069, Дои:10.1016 / S0097-3165 (03) 00049-9, МИСТЕР  1979545.
• Энгель, Конрад (1997), Теория Спернера, Энциклопедия математики и ее приложений, 65, Кембридж: Издательство Кембриджского университета, стр. х + 417, Дои:10.1017 / CBO9780511574719, ISBN  0-521-45206-6, МИСТЕР  1429390.
• Энгель, К. (2001) [1994], «Теорема Спернера», Энциклопедия математики, EMS Press
• Эрдеш, П. (1945), "Об одной лемме Литтлвуда и Оффорда" (PDF), Бюллетень Американского математического общества, 51 (12): 898–902, Дои:10.1090 / S0002-9904-1945-08454-7, МИСТЕР  0014608
• Любелл, Д. (1966), "Краткое доказательство леммы Спернера", Журнал комбинаторной теории, 1 (2): 299, Дои:10.1016 / S0021-9800 (66) 80035-2, МИСТЕР  0194348.
• Мешалкин, Л. (1963), «Обобщение теоремы Спернера о числе подмножеств конечного множества.», Теория вероятностей и ее приложения, 8 (2): 203–204, Дои:10.1137/1108023.
• Рота, Джан-Карло; Харпер, Л. Х. (1971), "Теория сопоставления, введение", Достижения в области теории вероятностей и смежных темах, Vol. 1, Нью-Йорк: Деккер, стр. 169–215, МИСТЕР  0282855.
• Спернер, Эмануэль (1928), "Ein Satz über Untermengen einer endlichen Menge", Mathematische Zeitschrift (на немецком), 27 (1): 544–548, Дои:10.1007 / BF01171114, HDL:10338.dmlcz / 127405, JFM  54.0090.06.

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

• Теорема Спернера в завязать узел
• Теорема Спернера на энциклопедии polymath1