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

Теорема Спернера, в дискретная математика, описывает максимально возможные семьи из конечные множества ни один из которых не содержит других наборов в семействе. Это один из центральных результатов теория экстремальных множеств. Он назван в честь Эмануэль Спернер, опубликовавший его в 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 п / 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}}$) обозначает п-Коэффициент Гаусса

${ 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