Теорема Спернера

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

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

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

• 1 Заявление
• 2 частичных заказа
• 3 Доказательство
• 4 Обобщения
  • 4.1 Никаких длинных цепей
  • 4.2 p -композиции множества
  • 4.3. Отсутствие длинных цепочек в p -композициях множества.
  • 4.4 Аналог проективной геометрии
  • 4.5. Отсутствие длинных цепочек в p -композициях проективного пространства.
• 5 См. Также
• 6 Ссылки
• 7 Внешние ссылки

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

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

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

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

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

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

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

${\ 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 до n, а затем применить неравенство 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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Бек и Заславский (2003) получили обобщение теоремы Рота – Харпера, подобное Мешалкину. В PG ( d, F q) последовательность Мешалкина длины p - это последовательность проективных подпространств, такая что никакое собственное подпространство PG ( d, F q) не содержит их всех, а их размерность равна. Теорема состоит в том, что семейство последовательностей Мешалкина длины p в PG ( d, F q) такое, что подпространства, появляющиеся в позиции i последовательностей, не содержат цепочки длины r, для каждого из которых не больше суммы наибольших из количество ${\ displaystyle (A_ {1}, \ ldots, A_ {p})}$${\ displaystyle d-p + 1}$${\ 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})},}$

где (в котором мы предполагаем, что) обозначает 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 : math / 0112068, DOI : 10,1006 / jcta.2002.3295, МР   1932078.
• Бек, Матиас; Заславский, Томас (2003), "Теорема Мешалкина для проективных геометрий", Журнал комбинаторной теории, серия A, 102 (2): 433–441, arXiv : math / 0112069, doi : 10.1016 / S0097-3165 (03) 00049 -9, Руководство по ремонту   1979545.
• Энгель, Конрад (1997), Теория Спернера, Энциклопедия математики и ее приложений, 65, Кембридж: Издательство Кембриджского университета, стр. x + 417, DOI : 10.1017 / CBO9780511574719, ISBN   0-521-45206-6, MR   1429390.
• Энгель, К. (2001) [1994], "Теорема Спернера", Энциклопедия математики, EMS Press
• Эрдеш, П. (1945), "Об одной лемме Литтлвуда и Оффорда" (PDF), Бюллетень Американского математического общества, 51 (12): 898–902, DOI : 10.1090 / S0002-9904-1945-08454-7, Руководство по ремонту   0014608
• Любелл, Д. (1966), «Краткое доказательство леммы Спернера», Журнал комбинаторной теории, 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, New York: Dekker, pp. 169–215, MR   0282855.
• Шпернеровы, Эмануэль (1928), "Ein Satz über Untermengen етек endlichen Менг", Mathematische Zeitschrift (на немецком языке), 27 (1): 544-548, DOI : 10.1007 / BF01171114, ЛВП : 10338.dmlcz / 127405, JFM   54,0090. 06.

• Теорема Спернера при разрубании узла
• Теорема Спернера о polymath1 вики