Теория Спернера

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

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

Заявление

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

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

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

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

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

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

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

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

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

{n \choose \lfloor {n/2}\rfloor }\geq {n \choose k}

и, таким образом,

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

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

\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,

что означает

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

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

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

{n \choose \lfloor {n/2}\rfloor }={n \choose k}

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

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

Обобщения

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

Никаких длинных цепочек

Цепь — это подсемейство $\{S_{0},S_{1},\dots ,S_{r}\}\subseteq {\mathcal {P}}(E)$ который полностью упорядочен, т.е. $S_{0}\subset S_{1}\subset \dots \subset S_{r}$ (возможно, после перенумерации). Цепочка имеет r + 1 членов и длину r . Семейство r без -цепей (также называемое r -семейством ) — это семейство подмножеств E , которое не содержит цепей длины r . Эрдеш (1945) доказал, что наибольший размер семейства r -бесцепных представляет собой сумму r крупнейших биномиальных коэффициентов. ${\binom {n}{i}}$ . Случай r = 1 — это теорема Спернера.

p -композиции множества

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

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

Отсутствие длинных цепей в p -композициях множества.

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

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

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

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

Отсутствие длинных цепей в p -композициях проективного пространства.

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

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

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

{\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}}

и

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},

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

См. также

Ссылки

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

Внешние ссылки

Теорема Спернера при разрубании узла
Теорема Спернера на вики-сайте Polymath1