Подсолнух (математика)

Нерешенная задача по математике :

Для любого размера подсолнуха, содержит ли подсолнух каждое множество множеств одинакового размера, мощность которого превышает некоторую экспоненту размера набора?

(еще нерешенные задачи по математике)

В математических областях теории множеств экстремальной комбинаторики подсолнух или и $\Delta$ -система ^[1] представляет собой совокупность множеств , в которой все возможные различные пары множеств имеют одно и то же пересечение . Это общее пересечение называется ядром подсолнечника.

Название возникает из-за визуального сходства с ботаническим подсолнухом, возникающего, когда диаграмма Венна набора подсолнухов устроена интуитивно. Предположим, что общие элементы набора подсолнухов сгруппированы вместе в центре диаграммы, а необщие элементы распределены по кругу вокруг общих элементов. Затем, когда диаграмма Венна будет завершена, лепесткообразные подмножества, окружающие общие элементы и один или несколько уникальных элементов, приобретут вид лепестков цветка.

существует крупный Основной исследовательский вопрос, возникающий применительно к подсолнухам, заключается в следующем: при каких условиях в данной коллекции севков подсолнух (подсолнух с множеством соцветий)? $\Delta$ -лемма , лемма о подсолнухе и гипотеза Эрдеша-Радо о подсолнухе дают последовательно более слабые условия, которые предполагают существование большого подсолнуха в данной коллекции, причем последняя является одной из самых известных открытых задач экстремальной комбинаторики. ^[2]

Формальное определение

Предполагать $W$ это система установленная $U$ , то есть совокупность подмножеств множества $U$ . Коллекция $W$ это подсолнух (или $\Delta$ -system ), если есть подмножество $S$ из $U$ такой, что для каждого отдельного $A$ и $B$ в $W$ , у нас есть $A\cap B=S$ . Другими словами, система множеств или совокупность множеств. $W$ это подсолнух, если все садится $W$ имеют одно и то же общее подмножество элементов. Элемент в $U$ либо находится в общем подмножестве $S$ или же появляется не более чем в одном из $W$ элементы. Нет элемента $U$ разделяется лишь некоторыми из $W$ подмножество, но не другие. Обратите внимание, что это пересечение, $S$ , может быть пустым ; совокупность попарно непересекающихся подмножеств также является подсолнухом. Точно так же коллекция множеств, каждое из которых содержит одни и те же элементы, также тривиально является подсолнухом.

Лемма и гипотеза о подсолнухе

Изучение подсолнухов обычно фокусируется на том, когда системы сеток содержат подсолнухи, в частности, когда система сеток достаточно велика, чтобы обязательно содержать подсолнечник.

В частности, исследователи анализируют функцию $f(k,r)$ для неотрицательных целых чисел $k,r$ , который определяется как наименьшее неотрицательное целое число $n$ такая, что для любой заданной системы $W$ такой, что каждый набор $S\in W$ имеет не более мощности $k$ , если $W$ имеет более чем $n$ устанавливает, затем $W$ содержит подсолнух $r$ наборы. Хотя не очевидно, что такое $n$ должна существовать, основной и простой результат Эрдёша и Радо , теорема о дельта-системе, указывает на то, что она существует.

Теорема Эрдеша-Радо о дельта-системе (следствие леммы о подсолнухе):

Для каждого $k>0$ , $r>0$ , есть целое число $f(k,r)$ так что если заданная система $F$ из $k$ -множество имеет мощность больше, чем $f(k,r)$ , затем $F$ содержит подсолнух размером $r$ .

В литературе, $W$ часто считается набором, а не коллекцией, поэтому любой набор может появиться в $W$ максимум один раз. Добавляя фиктивные элементы, достаточно рассматривать только системы множеств. $W$ так, что каждый набор в $W$ имеет мощность $k$ , поэтому часто лемму о подсолнечнике эквивалентно формулируют как « $k$ -единые» системы множеств. ^[3]

Лемма о подсолнухе

Эрдеш и Радо (1960 , стр. 86) доказали лемму о подсолнечнике , которая гласит, что ^[4]

f(k,r)\leq k!(r-1)^{k}.

То есть, если $k$ и $r$ являются целыми положительными числами , то система множеств $W$ мощности больше или равна $k!(r-1)^{k}$ наборов мощности $k$ содержит подсолнечник, по крайней мере, $r$ наборы.

Лемму Эрдеша-Радо о подсолнечнике можно доказать непосредственно методом индукции. Первый, $f(1,r)\leq r-1$ , поскольку заданная система $W$ должно быть коллекцией различных наборов размера один, и поэтому $r$ из этих наборов сделайте подсолнух. В общем случае предположим $W$ у него нет подсолнуха с $r$ наборы. Тогда рассмотрим $A_{1},A_{2},\ldots ,A_{t}\in W$ быть максимальным набором попарно непересекающихся множеств (т.е. $A_{i}\cap A_{j}$ является пустым множеством, если только $i=j$ , и каждый набор в $W$ пересекается с некоторыми $A_{i}$ ). Потому что мы предполагали, что $W$ не было подсолнуха такого размера $r$ , а совокупность попарно непересекающихся множеств — подсолнух, $t<r$ .

Позволять $A=A_{1}\cup A_{2}\cup \cdots \cup A_{t}$ . Поскольку каждый $A_{i}$ имеет мощность $k$ , мощность $A$ ограничен $kt\leq k(r-1)$ . Определять $W_{a}$ для некоторых $a\in A$ быть

W_{a}=\{S\setminus \{a\}\mid a\in S,\,S\in W\}.

Затем $W_{a}$ это устоявшаяся система, например $W$ , за исключением того, что каждый элемент $W_{a}$ имеет $k-1$ элементы. Кроме того, каждый подсолнух $W_{a}$ соответствует подсолнуху $W$ , просто добавив обратно $a$ к каждому набору. Это означает, что, по нашему предположению, $W$ нет подсолнуха такого размера $r$ , размер $W_{a}$ должен быть ограничен $f(k-1,r)-1$ .

Поскольку каждый набор $S\in W$ пересекается с одним из $A_{i}$ s, оно пересекается с $A$ , и поэтому оно соответствует хотя бы одному из множеств в $W_{a}$ :

|W|\leq \sum _{a\in A}|W_{a}|\leq |A|(f(k-1,r)-1)\leq k(r-1)f(k-1,r)-|A|\leq k(r-1)f(k-1,r)-1.

Следовательно, если $|W|\geq k(r-1)f(k-1,r)$ , затем $W$ содержит $r$ набор подсолнухов по размеру $k$ наборы. Следовательно, $f(k,r)\leq k(r-1)f(k-1,r)$ и отсюда следует теорема. ^[2]

Гипотеза Эрдеша-Радо о подсолнухе

Гипотеза о подсолнухе — это одна из нескольких вариаций гипотезы Эрдёша и Радо (1960 , стр. 86), согласно которой для каждого $r>2$ , $f(k,r)\leq C^{k}$ для некоторой константы $C>0$ в зависимости только от $r$ . Гипотеза остается широко открытой даже для фиксированных низких значений $r$ ; например $r=3$ ; неизвестно, является ли $f(k,3)\leq C^{k}$ для некоторых $C>0$ . ^[5] Статья Алвайса, Ловетта, Ву и Чжана 2021 года дает наилучший прогресс в направлении этой гипотезы, доказывая, что $f(k,r)\leq C^{k}$ для $C=O(r^{3}\log(k)\log \log(k))$ . ^[6]^[7] Через месяц после выхода первой версии своей статьи Рао усилил привязку к $C=O(r\log(rk))$ ; ^[8] текущая самая известная граница $C=O(r\log k)$ . ^[9]

Нижние границы подсолнечника

Эрдеш и Радо доказали следующую нижнюю оценку $f(k,r)$ . Это равносильно утверждению, что исходная лемма о подсолнечнике оптимальна в $r$ .

Теорема. $(r-1)^{k}\leq f(k,r).$

Доказательство.Для $k=1$ набор $r-1$ последовательность отдельных элементов — это не подсолнух.Позволять $h(k-1,r)$ обозначают размер наибольшего набора $k-1$ -комплекты без $r$ подсолнечник. Позволять $H$ быть таким набором. Возьмите дополнительный комплект $r-1$ элементы и добавьте по одному элементу в каждый набор в одном из $r-1$ непересекающиеся копии $H$ . Возьмем профсоюз $r-1$ непересекающиеся копии с добавленными элементами и обозначают это множество $H^{*}$ . Копии $H$ с добавленным элементом из $r-1$ раздел $H^{*}$ . У нас есть это, $(r-1)|H|\leq |H^{*}|$ . $H^{*}$ не содержит подсолнечника, поскольку любой выбор $r$ устанавливается, если в одном из непересекающихся разделов нет подсолнечника, исходя из предположения, что H не содержит подсолнечника. В противном случае, если $r$ наборы выбираются из нескольких наборов раздела, то из одного раздела необходимо выбрать два, поскольку есть только $r-1$ перегородки. Это означает, что по крайней мере два набора (а не все наборы) будут иметь общий элемент. Значит это не подсолнух $r$ наборы.

Более сильным результатом является следующая теорема:

Теорема. $f(a+b,r)\geq (f(a,r)-1)(f(b,r)-1)$

Доказательство. Позволять $F$ и $F^{*}$ быть двумя семьями, свободными от подсолнечника. Для каждого набора $A$ в F, добавьте каждый набор в $F^{*}$ к $A$ производить $|F^{*}|$ много наборов. Обозначим это семейство множеств $F_{A}$ . Возьмите союз $F_{A}$ общий $A$ в $F$ . В результате образуется семейство $|F^{*}||F|$ наборы без подсолнуха.

Наилучшая существующая нижняя оценка задачи Эрдоша-Радо «Подсолнух» для $r=3$ является $10^{\frac {k}{2}}\leq f(k,3)$ , благодаря Эботту, Хансену и Зауэру. ^[10]^[11] Эта граница не улучшалась более 50 лет.

Применение леммы о подсолнухе

Лемма о подсолнухе имеет множество приложений в теоретической информатике . Например, в 1986 году Разборов использовал лемму о подсолнухе, чтобы доказать, что язык клики требует $n^{\log(n)}$ Монотонные схемы (суперполиномиального) размера - прорыв в теории сложности схем на то время. Хостад, Юкна и Пудлак использовали его для доказательства нижних границ глубины. $3$ $AC_{0}$ схемы. Он также применялся при параметризованной сложности проблемы набора попаданий для разработки управляемых алгоритмов с фиксированным параметром для поиска небольших наборов элементов, которые содержат хотя бы один элемент из заданного семейства наборов. ^[12]

Аналог для бесконечных коллекций наборов

Версия $\Delta$ -лемма , которая по сути эквивалентна лемме Эрдеша-Радо $\Delta$ Теорема о -системе утверждает, что счетный набор k-множеств содержит счетный бесконечный подсолнух или $\Delta$ -система.

The $\Delta$ -лемма утверждает, что каждая несчетная совокупность конечных множеств содержит несчетное $\Delta$ -система.

The $\Delta$ -лемма — это комбинаторный теоретико-множественный инструмент, используемый в доказательствах для установления верхней границы размера набора попарно несовместимых элементов в принудительном частичном множестве . Например, его можно использовать в качестве одного из ингредиентов доказательства, показывающего, что оно согласуется с теорией множеств Цермело – Френкеля , согласно которой гипотеза континуума не выполняется. Его ввёл Шанин ( 1946 ).

Если $W$ это $\omega _{2}$ -размерная коллекция счетных подмножеств $\omega _{2}$ , и если гипотеза континуума верна, то существует $\omega _{2}$ -размерный $\Delta$ -подсистема. Позволять $\langle A_{\alpha }:\alpha <\omega _{2}\rangle$ перечислять $W$ . Для $\operatorname {cf} (\alpha )=\omega _{1}$ , позволять $f(\alpha )=\sup(A_{\alpha }\cap \alpha )$ . По лемме Фодора исправим $S$ стационарный в $\omega _{2}$ такой, что $f$ постоянно равен $\beta$ на $S$ .Строить $S'\subseteq S$ мощности $\omega _{2}$ такое, что всякий раз, когда $i<j$ находятся в $S'$ затем $A_{i}\subseteq j$ . Согласно гипотезе континуума, существуют только $\omega _{1}$ -множество счетных подмножеств $\beta$ , поэтому дальнейшим утончением мы можем стабилизировать ядро.

См. также

Набор крышек

Ссылки

Алвейс, Райан; Ловетт, Шачар; Ву, Кевен; Чжан, Цзяпэн (июнь 2020 г.), «Улучшенные границы леммы о подсолнечнике», Труды 52-го ежегодного симпозиума ACM SIGACT по теории вычислений , Ассоциация вычислительной техники, стр. 624–630, arXiv : 1908.08483 , doi : 10.1145/3357713.3384 234 , ISBN 978-1-4503-6979-4 , S2CID 201314765
Белл, Толсон; Чуэлуеча, Сучакри; Варнке, Лутц (2021), «Заметка о подсолнухах», Дискретная математика , 344 (7): 112367, arXiv : 2009.09327 , doi : 10.1016/j.disc.2021.112367 , MR 4240687 , S2CID 221818818
Деза, М .; Франкл, П. (1981), «Каждый большой набор равноотстоящих (0,+1,–1)-векторов образует подсолнух», Combinatorica , 1 (3): 225–231, doi : 10.1007/BF02579328 , ISSN 0209- 9683 , МР 0637827 , С2КИД 14043028
Эрдеш, Пол ; Радо, Р. (1960), «Теоремы пересечения систем множеств», Журнал Лондонского математического общества , вторая серия, 35 (1): 85–90, doi : 10.1112/jlms/s1-35.1.85 , ISSN 0024 -6107 , МР 0111692
Флум, Йорг; Гроэ, Мартин (2006), «Ядеризация набора попаданий», Теория параметризованной сложности , EATCS Ser. Тексты по теоретической информатике, Springer, стр. 210–212, doi : 10.1007/3-540-29953-X , ISBN. 978-3-540-29952-3 , МР 2238686
Джех, Томас (2003), Теория множеств , Спрингер
Кунен, Кеннет (1980), Теория множеств: введение в доказательства независимости , Северная Голландия, ISBN 978-0-444-85401-8
Рао, Ануп (25 февраля 2020 г.), «Кодирование для подсолнухов» , Дискретный анализ , 2020 (2): 11887, doi : 10.19086/da.11887 , S2CID 202558957
Рао, Ануп (2023), «Подсолнухи: от почвы к маслу» (PDF) , Bull. амер. Математика. Соц. , 60 (1): 29–38, doi : 10.1090/bull/1777
Шанин Н. А. (1946), "Одна теорема из общей теории множеств", К. Р. (Доклады) акад. наук. УРСС , Новая серия, 53 : 399–400
Тао, Теренс (2020), Лемма о подсолнечнике через энтропию Шеннона , Что нового (личный блог)

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

Тиманн, Рене. Лемма о подсолнухе Эрдеша и Радо (разработка формального доказательства в Isabelle/HOL, Архив формальных доказательств)

Примечания

^ Первоначальный термин для этой концепции был « $\Delta$ В последнее время термин «подсолнечник», возможно, введенный Деза и Франклом (1981) , постепенно заменяет его.
^ Jump up to: ^а ^б «Экстремальная комбинаторика III: некоторые основные теоремы» . Комбинаторика и многое другое . 28 сентября 2008 года . Проверено 10 декабря 2021 г.
^ Алвейс и др. (2020) , с. 3.
^ Косточка, Александр В. (2000), Альтёфер, Инго; Цай, Нин; Дуек, Гюнтер; Хачатрян, Левон (ред.), «Экстремальные проблемы Δ-систем» , Числа, информация и сложность , Бостон, Массачусетс: Springer US, стр. 143–150, doi : 10.1007/978-1-4757-6048-4_14 , ISBN 978-1-4757-6048-4 , получено 2 мая 2022 г.
^ Эбботт, Х.Л.; Хэнсон, Д; Зауэр, Н. (май 1972 г.). «Теоремы пересечения систем множеств» . Журнал комбинаторной теории, серия А. 12 (3): 381–389. дои : 10.1016/0097-3165(72)90103-3 .
^ Алвейс и др. (2020) .
^ «Журнал «Кванта» — освещение науки» . Журнал Кванта . Проверено 10 ноября 2019 г.
^ Рао (2020) .
^ Белл, Чуэлуеча и Варнке (2021) .
^ Эбботт, Х.Л.; Хэнсон, Д; Зауэр, Н. (май 1972 г.). «Теоремы пересечения систем множеств» . Журнал комбинаторной теории, серия А. 12 (3): 381–389. дои : 10.1016/0097-3165(72)90103-3 .
^ Нижние границы проблемы подсолнечника https://mathoverflow.net/a/420288/12176
^ Флум и Гроэ (2006) .

[1] Первоначальный термин для этой концепции был « $\Delta$ В последнее время термин «подсолнечник», возможно, введенный Деза и Франклом (1981) , постепенно заменяет его.

[kalai-2] Jump up to: ^а ^б «Экстремальная комбинаторика III: некоторые основные теоремы» . Комбинаторика и многое другое . 28 сентября 2008 года . Проверено 10 декабря 2021 г.

[FOOTNOTEAlweissLovettWuZhang20203-3] Алвейс и др. (2020) , с. 3.

[4] Косточка, Александр В. (2000), Альтёфер, Инго; Цай, Нин; Дуек, Гюнтер; Хачатрян, Левон (ред.), «Экстремальные проблемы Δ-систем» , Числа, информация и сложность , Бостон, Массачусетс: Springer US, стр. 143–150, doi : 10.1007/978-1-4757-6048-4_14 , ISBN 978-1-4757-6048-4 , получено 2 мая 2022 г.

[5] Эбботт, Х.Л.; Хэнсон, Д; Зауэр, Н. (май 1972 г.). «Теоремы пересечения систем множеств» . Журнал комбинаторной теории, серия А. 12 (3): 381–389. дои : 10.1016/0097-3165(72)90103-3 .

[FOOTNOTEAlweissLovettWuZhang2020-6] Алвейс и др. (2020) .

[7] «Журнал «Кванта» — освещение науки» . Журнал Кванта . Проверено 10 ноября 2019 г.

[FOOTNOTERao2020-8] Рао (2020) .

[FOOTNOTEBellChueluechaWarnke2021-9] Белл, Чуэлуеча и Варнке (2021) .

[10] Эбботт, Х.Л.; Хэнсон, Д; Зауэр, Н. (май 1972 г.). «Теоремы пересечения систем множеств» . Журнал комбинаторной теории, серия А. 12 (3): 381–389. дои : 10.1016/0097-3165(72)90103-3 .

[11] Нижние границы проблемы подсолнечника https://mathoverflow.net/a/420288/12176

[FOOTNOTEFlumGrohe2006-12] Флум и Гроэ (2006) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]