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

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

Теорема Шпернера, в дискретной математике, описывает максимально возможные семьи из конечных множеств, ни одна из которых содержат любые другие наборы в семье. Это один из центральных результатов экстремальной теории множеств. Он назван в честь Эмануэля Спернера, опубликовавшего его в 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 нечетное. Для этого выбора количество комплектов в семье составляет. ( п п / 2 ) {\ displaystyle {\ tbinom {n} {\ lfloor n / 2 \ rfloor}}}

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

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

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

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

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

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

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

( п п / 2 ) ( п k ) {\ Displaystyle {п \ выбрать \ lfloor {п / 2} \ rfloor} \ geq {п \ выбрать k}}

и поэтому,

s k ( п п / 2 ) s k ( п k ) . {\ displaystyle {s_ {k} \ over {n \ choose \ lfloor {n / 2} \ rfloor}} \ leq {s_ {k} \ over {n \ choose k}}.}

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

k знак равно 0 п s k ( п п / 2 ) k знак равно 0 п s k ( п k ) 1 , {\ 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,}

что значит

| S | знак равно k знак равно 0 п s k ( п п / 2 ) . {\ displaystyle | S | = \ sum _ {k = 0} ^ {n} s_ {k} \ leq {n \ choose \ lfloor {n / 2} \ rfloor}.}

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

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

( п п / 2 ) знак равно ( п k ) {\ Displaystyle {п \ выбрать \ lfloor {п / 2} \ rfloor} = {п \ выбрать k}}

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

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

Обобщения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[ d + 1 п 1 ] [ d + 1 - п 1 п 2 ] [ d + 1 - ( п 1 + + п п - 1 ) п п ] {\ 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}}}

и

s 2 ( п 1 , , п п ) знак равно п 1 п 2 + п 1 п 3 + п 2 п 3 + п 1 п 4 + + п п - 1 п п , {\ 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},}

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

Смотрите также
использованная литература
внешние ссылки
Последняя правка сделана 2024-01-09 03:17:42
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте