Введение
теорема о симплексах
Теорема Спернера в дискретной математике описывает максимально возможные семейства конечных множеств, ни одно из которых не является подмножеством другого множества из этого семейства. Это один из центральных результатов в экстремальной теории множеств. Она названа в честь Эммануэля Спернера, опубликовавшего её в 1928 году. Этот результат иногда называют леммой Спернера, однако название "лемма Спернера" также относится к несвязанному результату о раскраске триангуляций. Чтобы различать эти два результата, теорему о размере семейства Спернера чаще называют теоремой Спернера.
Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, who published it in 1928. This result is sometimes called Sperner's lemma, but the name "Sperner's lemma" also refers to an unrelated result on coloring triangulations. To differentiate the two results, the result on the size of a Sperner family is now more commonly known as Sperner's theorem.
Частичные заказы
Теорема Спернера также может быть сформулирована в терминах ширины частичного порядка. Семейство всех подмножеств множества из n элементов (его булеан, или множество мощностей) может быть частично упорядочено по включению множеств; в этом частичном порядке два различных элемента считаются несравнимыми, если ни один из них не содержит другой. Ширина частичного порядка – это максимальное число элементов в антицепи, то есть в множестве попарно несравнимых элементов. Переводя эту терминологию на язык теории множеств, антицепь – это просто семейство Спернера, а ширина частичного порядка – это максимальное число множеств в семействе Спернера. Таким образом, теорема Спернера может быть сформулирована и так: ширина порядка включения в булеане равна… Градированное частично упорядоченное множество называется обладающим свойством Спернера, если одна из его наибольших антицепей состоит из множества элементов, все из которых имеют одинаковый ранг. В этой терминологии теорема Спернера утверждает, что частично упорядоченное множество всех подмножеств конечного множества, частично упорядоченное по включению множеств, обладает свойством Спернера.
A graded partially ordered set is said to have the Sperner property when one of its largest antichains is formed by a set of elements that all have the same rank. In this terminology, Sperner's theorem states that the partially ordered set of all subsets of a finite set, partially ordered by set inclusion, has the Sperner property.
Обобщения
Существует несколько обобщений теоремы Спернера для подмножеств решетки всех подмножеств E.
Без длинных цепей
Цепь — это подсемейство, которое полностью упорядочено, то есть (возможно, после перенумерации). Цепь содержит r + 1 элемент и имеет длину r. r-свободная семейство цепей (также называемое r-семейством) — это семейство подмножеств E, не содержащее цепь длины r. Доказано, что максимальный размер r-свободного семейства цепей равен сумме r наибольших биномиальных коэффициентов. Случай r = 1 — это теорема Спернера.
p-состав множества
В множестве p-кортежей подмножеств E мы говорим, что p-кортеж ≤ другого, если для каждого i = 1, 2, ..., p. Мы называем p-композицией E, если множества образуют разбиение E. Доказано, что максимальный размер антицепи из p-композиций равен наибольшему p-му мультиномиальному коэффициенту, то есть коэффициенту, в котором все ni максимально близки друг к другу (то есть отличаются не более чем на 1). Мешалкин доказал это, доказав обобщенное неравенство LYM. В случае p = 2 это теорема Спернера, поскольку тогда и предположения сводятся к тому, что множества образуют семейство Спернера.
Нет длинных цепей в p-составлениях набора
объединили теоремы Эрдеша и Мешалкина, адаптировав доказательство Мешалкина его обобщенного неравенства LYM. Они показали, что максимальный размер семейства из p композиций, для которых множества в i-й позиции p-кортежей, без учета повторений, не содержат цепей длины r, для всех i (но не обязательно для i = p), не превосходит суммы наибольших p мультиномиальных коэффициентов.
Проективная геометрия аналоговая
В конечной проективной геометрии PG(d, Fq) размерности d над конечным полем порядка q, пусть – семейство всех подпространств. При частичном упорядочении по включению множеств, это семейство образует решетку. Было доказано, что наибольший размер антицепи в равен наибольшему гауссовскому коэффициенту – это аналог теоремы Спернера в проективной геометрии, или q-аналог. Они также доказали, что наибольший размер семейства, свободного от r-цепей, в равен сумме r наибольших гауссовских коэффициентов. Их доказательство основано на проективном аналоге неравенства LYM.