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

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

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

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

Предположим, что есть система множеств над , то есть совокупность подмножеств множества . Совокупность является подсолнечником (или -системой ), если существует подмножество из , такое что для каждого отдельного и в , мы имеем . Другими словами, система множеств или совокупность множеств является подсолнечником, если все множества в имеют одно и то же общее подмножество элементов. Элемент в либо находится в общем подмножестве , либо появляется не более чем в одном из элементов. Ни один элемент из не является общим только для некоторых из подмножества, но не для других. Обратите внимание, что это пересечение, , может быть пустым ; совокупность попарно непересекающихся подмножеств также является подсолнечником. Аналогично, совокупность множеств, каждое из которых содержит одни и те же элементы, также тривиально является подсолнечником.${\displaystyle W}$${\displaystyle U}$${\displaystyle U}$${\displaystyle W}$${\displaystyle \Дельта}$${\displaystyle S}$${\displaystyle U}$ ${\displaystyle А}$${\displaystyle Б}$${\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 к,р}$ ${\displaystyle n}$${\displaystyle W}$${\displaystyle S\in W}$${\displaystyle к}$${\displaystyle W}$${\displaystyle n}$${\displaystyle W}$${\displaystyle r}$${\displaystyle n}$

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

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

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

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

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

То есть, если и являются положительными целыми числами , то система множеств мощности, большей или равной множеств мощности, содержит подсолнух с не менее чем множествами.${\displaystyle к}$${\displaystyle r}$${\displaystyle W}$${\displaystyle к!(r-1)^{к}}$${\displaystyle к}$${\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 Вт}$${\displaystyle A_{i}\cap A_{j}}$${\displaystyle i=j}$${\displaystyle W}$${\displaystyle A_{i}}$${\displaystyle W}$${\displaystyle r}$${\displaystyle т<р}$

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

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

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

Поскольку каждое множество пересекается с одним из , оно пересекается с , и поэтому оно соответствует по крайней мере одному из множеств в :${\displaystyle S\in W}$${\displaystyle A_{i}}$${\displaystyle А}$${\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 к}$${\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 С>0}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r=3}$${\displaystyle f(k,3)\leq C^{k}}$${\displaystyle С>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 к=1}$${\displaystyle r-1}$${\displaystyle h(k-1,r)}$${\displaystyle к-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 А}$${\displaystyle F^{*}}$${\displaystyle А}$${\displaystyle |F^{*}|}$${\displaystyle F_{A}}$${\displaystyle F_{A}}$${\displaystyle А}$${\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 \Дельта}$${\displaystyle \Дельта}$${\displaystyle \Дельта}$

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

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

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

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

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