Теорема Шпернера , в дискретной математике , описывает максимально возможные семьи из конечных множеств , ни одна из которых содержат любые другие наборы в семье. Это один из центральных результатов экстремальной теории множеств . Он назван в честь Эмануэля Спернера , опубликовавшего его в 1928 году.
Этот результат иногда называют леммой Спернера, но название « лемма Спернера » также относится к несвязанному результату о раскраске триангуляций. Чтобы различать эти два результата, результат о размере семьи Спернера теперь более известен как теорема Спернера.
Заявление
Семейство множеств , в которых ни один из наборов не является строгим подмножество другого, называется семейством шпернеровых , или антицепь множеств, или помехи. Например, семейство k -элементных подмножеств n -элементного множества является семейством Спернера. Ни один набор в этом семействе не может содержать другие, потому что содержащий набор должен быть строго больше, чем набор, который он содержит, а в этом семействе все наборы имеют равный размер. Значение k, которое позволяет этому примеру иметь как можно больше наборов, равно n / 2, если n четно, или ближайшему к n / 2 целому числу, если n нечетное. Для этого выбора количество наборов в семье равно.
Теорема Спернера утверждает, что эти примеры являются наибольшими возможными семействами Спернера над n -элементным множеством. Формально теорема утверждает, что,
- для каждого семейства Спернеров S , объединение которого состоит из n элементов, а также
- равенство выполняется тогда и только тогда, когда S состоит из всех подмножеств n -элементного множества, имеющих размер или все, что имеет размер .
Частичные заказы
Теорема Спернера также может быть сформулирована в терминах ширины частичного порядка . Семейство всех подмножеств n -элементного множества (его мощности ) может быть частично упорядочено включением множества; в этом частичном порядке два различных элемента называются несравнимыми, если ни один из них не содержит другого. Ширина частичного порядка - это наибольшее количество элементов в антицепи , наборе попарно несравнимых элементов. Если перевести эту терминологию на язык множеств, антицепь - это просто семейство Спернера, а ширина частичного порядка - это максимальное количество множеств в семье Спернера. Таким образом, другой способ сформулировать теорему Спернера состоит в том, что ширина порядка включения на множестве степеней равна.
Градуированное частично упорядоченное множество называется имеет свойство шпернеровых , когда один из крупнейших антицепей образованно множеством элементов , которые все имеют одинаковый ранг. В этой терминологии теорема Спернера утверждает, что частично упорядоченное множество всех подмножеств конечного множества, частично упорядоченное включением множества, обладает свойством Спернера.
Доказательство
Существует множество доказательств теоремы Спернера, каждое из которых приводит к различным обобщениям (см. Anderson (1987)).
Следующее доказательство принадлежит Любеллу (1966) . Пусть ы к обозначит число K множеств в S . Для всех 0 ≤ k ≤ n ,
и поэтому,
Поскольку S является антицепью, мы можем просуммировать по вышеуказанному неравенству от k = 0 до n, а затем применить неравенство LYM, чтобы получить
что значит
Это завершает доказательство части 1.
Чтобы иметь равенство, все неравенства в предыдущем доказательстве должны быть равенствами. С
если и только если или же заключаем, что равенство означает, что S состоит только из наборов размеров или же Для четных n это завершает доказательство части 2.
Для нечетных n необходимо проделать дополнительную работу, которую мы здесь опускаем, поскольку она сложна. См. Anderson (1987), стр. 3–4.
Обобщения
Существует несколько обобщений теоремы Спернера для подмножеств частично упорядоченное множество всех подмножеств Е .
Без длинных цепей
Цепь является подсемейство который полностью упорядочен, т. е. (возможно, после перенумерации). Цепочка состоит из r + 1 элемента и имеет длину r . Г -цепь свободной семьи (также называется г -семейством ) представляет собой семейство подмножеств Е , который не содержит цепочку длины г . Эрдеш (1945) доказал, что наибольший размер семейства без r- цепочек представляет собой сумму r наибольших биномиальных коэффициентов. Случай r = 1 - это теорема Спернера.
p -композиции множества
В комплекте из р -наборов подмножеств Е , мы скажем, р -кратного ≤ еще один, если для каждого i = 1,2, ..., p . Мы называемр -композиция из Е , если множестваобразуют разбиение Е . Мешалкин (1963) доказал, что максимальный размер антицепи p- композиций есть наибольший p -мультиномиальный коэффициентто есть коэффициент, в котором все n i максимально равны (то есть различаются не более чем на 1). Мешалкин доказал это, доказав обобщенное неравенство LYM.
Случай p = 2 - это теорема Спернера, потому что тогда а предположения сводятся к множествам быть семьей Спернер.
Отсутствие длинных цепочек в p -композициях множества
Бек и Заславский (2002) объединили теоремы Эрдеша и Мешалкина, адаптировав доказательство Мешалкиным его обобщенного неравенства LYM. Они показали, что наибольший размер семейства p -композиций такой, что наборы в i-й позиции p- наборов, игнорируя дублирования, свободны от r- цепочек для каждого(но не обязательно для i = p ), не больше суммынаибольшие p -мультиномиальные коэффициенты.
Аналог проективной геометрии
В конечной проективной геометрии PG ( d , F q ) размерности d над конечным полем порядка q пусть- семейство всех подпространств. При частичном упорядочении включением множества это семейство представляет собой решетку. Рота и Харпер (1971) доказали, что наибольший размер антицепи в- наибольший коэффициент Гаусса это аналог проективной геометрии, или q- аналог теоремы Спернера.
Они также доказали, что самый большой размер семьи без r- цепей впредставляет собой сумму r наибольших гауссовских коэффициентов. Их доказательство проводится с помощью проективного аналога неравенства LYM.
Никаких длинных цепочек в p- композициях проективного пространства
Бек и Заславский (2003) получили обобщение теоремы Рота – Харпера, подобное Мешалкину. В PG ( d , F q ) последовательность Мешалкина длины p - это последовательностьпроективных подпространств таких, что никакое собственное подпространство PG ( d , F q ) не содержит их всех, а их размерности в сумме равны. Теорема состоит в том, что семейство последовательностей Мешалкина длины p в PG ( d , F q ) такое, что подпространства, появляющиеся в позиции i последовательностей, не содержат цепочки длины r для каждого не больше суммы наибольших количества
где (в котором мы предполагаем, что ) обозначает 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.
- Рота, Джан-Карло ; Харпер, LH (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 вики