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