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

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

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

(еще нерешенные проблемы по математике)

Совокупность множеств, в которой каждые два множества имеют одно и то же пересечение

Математический подсолнух можно изобразить как цветок. Ядро подсолнуха — это коричневая часть в середине, а каждый набор подсолнуха — это объединение лепестка и ядра.

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

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

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

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

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

Лемма и гипотеза о подсолнечнике

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

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

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

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

В литературе часто предполагается, что это множество, а не коллекция, так что любое множество может появиться в не более одного раза. Добавляя фиктивные элементы, достаточно рассматривать только такие системы множеств, что каждое множество в имеет мощность , поэтому часто лемма о подсолнечнике эквивалентно формулируется как верная для " -однородных" систем множеств. ^[3] ${\displaystyle W}$ ${\displaystyle W}$ ${\displaystyle W}$ ${\displaystyle W}$ ${\displaystyle k}$ ${\displaystyle k}$

Лемма подсолнечника

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

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

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

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

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

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

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

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

${\displaystyle |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.}$

Следовательно, если , то содержит множество sunflower размера sets. Отсюда и следует теорема. ^[2] ${\displaystyle |W|\geq k(r-1)f(k-1,r)}$ ${\displaystyle W}$ ${\displaystyle r}$ ${\displaystyle k}$ ${\displaystyle f(k,r)\leq k(r-1)f(k-1,r)}$

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

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

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

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

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

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

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

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

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

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

Приложения леммы о подсолнечнике

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

Аналог для бесконечных наборов множеств

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

-Лемма утверждает , что каждая несчетная совокупность конечных множеств содержит несчетную -систему. ${\displaystyle \Delta }$ ${\displaystyle \Delta }$

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

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

Смотрите также

• Набор колпачков

Ссылки

• Alweiss, Ryan; Lovett, Shachar; Wu, Kewen; Zhang, Jiapeng (июнь 2020 г.), «Улучшенные границы для леммы о подсолнечнике», Труды 52-го ежегодного симпозиума ACM SIGACT по теории вычислений , Ассоциация вычислительной техники, стр. 624–630, arXiv : 1908.08483 , doi : 10.1145/3357713.3384234, 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, MR  0637827, S2CID  14043028
• Эрдёш, Пол ; Радо, Р. (1960), «Теоремы пересечения для систем множеств», Журнал Лондонского математического общества , Вторая серия, 35 (1): 85–90, doi :10.1112/jlms/s1-35.1.85, ISSN  0024-6107, MR  0111692
• Флум, Йорг; Гроэ, Мартин (2006), «Кернализация множества попаданий», Параметризованная теория сложности , EATCS Серия Тексты по теоретической информатике, 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.02.2020), «Кодирование подсолнухов», Дискретный анализ , 2020 (2): 11887, doi : 10.19086/da.11887 , S2CID  202558957
• Рао, Ануп (2023), «Подсолнухи: от почвы до масла» (PDF) , Bull. Amer. Math. Soc. , 60 (1): 29–38, doi : 10.1090/bull/1777
• Шанин, Н.А. (1946), «Теорема из общей теории множеств», Доклады АН УССР , Новая серия, 53 : 399–400
• Тао, Теренс (2020), Лемма о подсолнечнике через энтропию Шеннона, Что нового (личный блог)

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

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

Примечания

1. Первоначальный термин для этой концепции был « -система». В последнее время термин «подсолнух», возможно, введенный Деза и Франклом (1981), постепенно заменяет его. ${\displaystyle \Delta }$
2. "Extremal Combinatorics III: Some Basic Theorems". Комбинаторика и многое другое . 28 сентября 2008 г. Получено 10 декабря 2021 г.
3. Альвейс и др. (2020), стр. 3.
4. Косточка, Александр В. (2000), Альтхёфер, Инго; Кай, Нинг; Дюк, Гюнтер; Хачатрян, Левон (ред.), «Экстремальные задачи в Δ-системах», Numbers, Information and Complexity , Бостон, Массачусетс: Springer US, стр. 143–150, doi :10.1007/978-1-4757-6048-4_14, ISBN 978-1-4757-6048-4, получено 2022-05-02
5. Эбботт, HL; Хансон, D; Зауэр, N (май 1972). «Теоремы пересечения для систем множеств». Журнал комбинаторной теории, серия A. 12 ( 3): 381–389. doi : 10.1016/0097-3165(72)90103-3 .
6. Альвейс и др. (2020).
7. "Quanta Magazine - Illuminating Science". Quanta Magazine . Получено 10.11.2019 .
8. Рао (2020).
9. Белл, Чуэлуеча и Варнке (2021).
10. Эбботт, HL; Хансон, D; Зауэр, N (май 1972). «Теоремы пересечения для систем множеств». Журнал комбинаторной теории, серия A. 12 ( 3): 381–389. doi : 10.1016/0097-3165(72)90103-3 .
11. Нижние оценки для задачи о подсолнухе https://mathoverflow.net/a/420288/12176
12. Флум и Гроэ (2006).