Состояние системы подсолнечника

Я интересуюсь системой подсолнечника и ее приложениями в информатике.

Для данной Вселенной и набора из k множеств A i называется системой k-подсолнечника, если A i ∩ A j = Y для всех i ≠ j . И Y называется ядром, а A i - Y называется лепестками. $U$$k$$A_i$$A_i \cap A_j = Y$$i \neq j$$Y$$A_i - Y$

Семейство наборов $F$ называется равномерным - все содержащиеся в нем множества содержат s элементов.$s$$s$

Erdos и Rado доказали , что для единообразного семейства множеств F , F должна содержать K -sunflower системы лепестков , если | F | > с ! ( $s$$F$$F$$k$ .$|F| > s!(k-1)^s$

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

Эрдош высказал предположение , что для каждого существует постоянная ç K таким образом, что верхняя граница должна быть C сек к каждой ев -равномерная семьи F . (Гипотеза подсолнечника)$k$$c_k$$c_k^s$$s$$F$

К сожалению, эта гипотеза все еще открыта для .$k=3$

Вот что я хочу знать.

Если мы ограничим количество элементов во вселенной .Suppose | U | = U . Тогда проблема оказывается:$U$$|U|$$u$

Для данной вселенной с элементами и s -однородным семейством F множеств, содержащих элементы в U , мы предположили, что можем найти последовательность констант c 1 , c 2 , c 3 , ... такую, что каждое s -однородное семейство F содержит 3- подсолнечная система, если | F | > с с я и | $u$$s$$F$$U$$c_1$$c_2$$c_3$$s$$F$$3$$|F|>$ $c_i^s$ .$|U|=i$

Более того, если бы мы могли доказать, что последовательность сходится к константе c , то, похоже, мы можем доказать гипотезу подсолнечника.$c_i$$c$

Но я не могу найти такой результат. Возможно, такой подход слишком глуп или слишком сложен.

Может ли кто-нибудь представить современное состояние леммы подсолнечника и гипотезы (конечная версия тоже в порядке).

Вот кое-что, что я могу предоставить. В книге Юнки есть глава «Экстремальная комбинаторика».

Статья выше является одним из его приложений (конечная версия)

О подсолнухах и умножении матриц N Alon et.al

ЭРДЁШ подсолнечника гипотеза , кажется, очень трудно после того, как в настоящее время более полувека (!) быть открытым. Вы уже перечислили некоторые из самых лучших и последних ссылок на Subj, которые было бы очень трудно победить (недавняя статья Алонса, книга Юкнаса по комбинаторике). статья Алона весьма примечательна тем, что вновь связывает эту гипотезу с нижними границами умножения матриц - области, в которой недавно произошел новаторский прогресс в результатах Уильямса. [4]

Вы можете найти дальнейшую трактовку, в основном приложения к теории экстремальных цепей (нижние границы 1-й цепи, открытые Разборовым и расширенные другими), в выдающейся книге Юкны [1].

Одним из примечательных / связанных недавних ссылок по этим направлениям, по-видимому, пока не столь широко известным или цитируемым, является [2] Россман с новым направлением применения (случайные графы Эрдоша-Реньи над монотонными цепями), который доказывает расширенные и / или более сильные результаты на "квази" подсолнухах. работа является результатом его докторской диссертации [3]. из реферата

Мы представляем новый вариант подсолнечника и доказываем аналог леммы подсолнечника, который может представлять самостоятельный интерес.

[1] Сложность, достижения и границы булевых функций

[2] Монотонная сложность k-клики на случайных графах (2009) Россман

[3] Средняя сложность обнаружения клик по Россману

[4] Комментарий к прорыву Уильямса по нижней границе матричного произведения Р. Дж. Липтонс Годелс Потерянное письмо блог

[5] Подробные материалы о подсолнухах