Гипотеза о замкнутых множествах

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

Если любые два множества в некотором конечном семействе множеств имеют объединение, которое также принадлежит этому семейству, должен ли какой-либо элемент принадлежать хотя бы половине множеств в семействе?

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

Гипотеза об объединенно-замкнутых множествах , также известная как гипотеза Франкла , является открытой проблемой комбинаторики, поставленной Петером Франклом в 1979 году. Семейство множеств называется объединенно-замкнутым, если объединение любых двух множеств из семейства принадлежит семья. Гипотеза гласит :

Для каждого конечного семейства множеств, замкнутого в объединение, кроме семейства, содержащего только пустое множество , существует элемент, который принадлежит по крайней мере половине множеств в семействе.

Профессор Тимоти Гауэрс назвал эту задачу « одной из самых известных открытых задач в комбинаторике » и сказал, что эта гипотеза « она привлекла множество ложных доказательств кажется, что она должна быть простой (и в результате на протяжении многих лет ). Хороший способ понять, почему это непросто, — потратить день, пытаясь доказать это. Тот умный аргумент об усреднении, который вы имели в виду, не работает… » ^[1]

Пример

Семейство наборов

\varnothing ,\{1\},\{1,2\},\{2,3,4\},\{1,2,3,4\}

состоит из пяти различных наборов и является замкнутым. Элемент $1$ содержится в трех из пяти наборов (как и элемент $2$ ), таким образом, в этом случае гипотеза верна.

Основные результаты

Легко показать, что если объединенное семейство содержит одноэлементный элемент $\{a\}$ (как в примере выше), то элемент $a$ должно встречаться как минимум в половине наборов семейства.

Если существует контрпример к гипотезе, то существует и контрпример, состоящий только из конечных множеств. Поэтому без ограничения общности будем считать, что все множества данного объединенно-замкнутого семейства конечны. ^[2]

Учитывая конечное непустое множество $U$ , набор мощности $P(U)$ состоящее из подмножеств всех $U$ является закрытым профсоюзом. Каждый элемент $U$ содержится ровно в половине подмножеств $U$ . Поэтому, вообще говоря, мы не можем требовать, чтобы элемент содержался более чем в половине множеств семейства: оценка гипотезы точна.

Эквивалентные формы

Формулировка пересечения

Гипотеза о замкнутом множестве верна тогда и только тогда, когда система множеств $X$ который является замкнутым на пересечение, содержит элемент $U(X)$ не более чем в половине наборов $X$ , где $U(X)$ - это совокупность вселенной, т.е. объединение всех членов системы $X$ .

Следующие факты показывают эквивалентность.

Во-первых, мы показываем, что система множеств является объединенно-замкнутой тогда и только тогда, когда ее дополнение замкнуто по пересечению.

Лемма 1. Если $X$ представляет собой замкнутое объединением семейство множеств со вселенной $U(X)$ , семейство дополнительных множеств к множествам в $X$ закрыт под перекрёстком .

Доказательство.Определим дополнение системы множеств $X$ как $X^{c}:=\{U(X)-S:S\in X\}$ .

Позволять $X_{1}$ , $X_{2}$ быть произвольными множествами в $X$ и так $U(X)-X_{1}$ и $U(X)-X_{2}$ оба в $X^{c}$ . С $X$ является закрытым профсоюзом, $X_{1}\cup X_{2}=X_{3}$ находится в $X$ , и, следовательно, дополнение $X_{3}$ , $U(X)-X_{3}$ находится в $X^{c}$ , элементы ни в одном $X_{1}$ , ни $X_{2}$ .

И это как раз и есть пересечение дополнений $X_{1}$ и $X_{2}$ , $(U(X)-X_{1})\cap (U(X)-X_{2})$ . Поэтому, $X$ является объединенно-замкнутым тогда и только тогда, когда дополнение $X$ , $X^{c}$ перекрёсток закрыт.

Во-вторых, мы показываем, что если система множеств содержит элемент хотя бы в половине множеств, то ее дополнение содержит элемент не более чем в половине.

Лемма 2. Система множеств. $X$ содержит элемент в половине своих наборов тогда и только тогда, когда система дополнительных множеств $X$ , $X^{*}$ содержит элемент не более чем в половине своих наборов.Доказательство. Тривиально.

Следовательно, если $X$ представляет собой замкнутое объединением семейство множеств, семейство множеств, дополняющих множества в $X$ относительно Вселенной $U(X)$ замкнут относительно пересечения, а элемент, принадлежащий хотя бы половине множеств $X$ принадлежит не более чем половине дополнительных множеств. Таким образом, эквивалентная форма гипотезы (форма, в которой она была первоначально сформулирована) состоит в том, что для любого замкнутого пересечением семейства множеств, содержащего более одного множества, существует элемент, принадлежащий не более чем половине множеств из семья.

Решеточная формулировка

Хотя гипотеза Франкла сформулирована выше в терминах семейств множеств, она также была сформулирована и изучена как вопрос теории решеток . Решетка частично — это упорядоченный набор , в котором для двух элементов x и y меньший или равный им обоим (пересечение x и существует уникальный наибольший элемент , y ) , и уникальный наименьший элемент, больший или равный им обоим. ( соединение x . и y ) Семейство всех подмножеств множества S , упорядоченное по включению множества, образует решетку, в которой соединение представлено теоретико -множественным пересечением, а соединение представлено теоретико-множественным объединением; решетка, образованная таким образом, называется булевой решеткой .Теоретико-решеточная версия гипотезы Франкла состоит в том, что в любой конечной решетке существует элемент x , который не является соединением каких-либо двух меньших элементов, и такой, что количество элементов, больших или равных x, составляет не более половины решетки, с равенством только в том случае, если решетка является булевой решеткой. Как показывает Абэ (2000) , это утверждение о решетках эквивалентно гипотезе Франкла для множеств, замкнутых в объединении: каждая решетка может быть переведена в семейство множеств, замкнутых в объединение, и каждое семейство множеств, замкнутых в объединение, может быть переведено в решетку, так что истинность гипотезы Франкла для переведенного объекта подразумевает истинность гипотезы для исходного объекта. Известно, что эта теоретико-решеточная версия гипотезы верна для нескольких естественных подклассов решеток. ^[3] но в общем случае остается открытым.

Теоретико-графовая формулировка

Другая эквивалентная формулировка гипотезы об объединенно-замкнутых множествах использует теорию графов . В неориентированном графе Независимый набор — это набор вершин, ни одна из которых не является смежной; независимое множество является максимальным , если оно не является подмножеством большего независимого множества. В любом графе «тяжелые» вершины, входящие более чем в половину максимальных независимых множеств, сами должны образовывать независимое множество. Итак, если граф непустой, всегда существует хотя бы одна нетяжелая вершина, вершина, которая встречается не более чем в половине максимальных независимых множеств. Графическая формулировка гипотезы об объединении-замкнутых множествах утверждает, что каждый конечный непустой граф содержит две смежные нетяжелые вершины. Это автоматически верно, когда граф содержит нечетный цикл , поскольку независимый набор всех тяжелых вершин не может покрыть все ребра цикла. Поэтому более интересный случай гипотезы — это двудольные графы , у которых нет нечетных циклов. Другая эквивалентная формулировка гипотезы состоит в том, что в каждом двудольном графе существуют две вершины, по одной на каждой стороне двудольного деления, такие, что каждая из этих двух вершин принадлежит не более чем половине максимальных независимых множеств графа. Известно, что эта гипотеза справедлива для хордальные двудольные графы , двудольные последовательно-параллельные графы и двудольные графы максимальной степени три. ^[4]

Частичные результаты

Гипотеза была доказана для многих особых случаев семейств объединенных замкнутых множеств. В частности, известно, что это справедливо для

семьи максимум из 46 комплектов, ^[5]
семейства множеств, объединение которых содержит не более 11 элементов, ^[6]
семейства множеств, в которых наименьшее множество имеет один или два элемента, ^[7]
семьи, состоящие как минимум $({\tfrac {1}{2}}-\varepsilon )2^{n}$ подмножества $n$ -множество элементов, для некоторой константы $\varepsilon >0$ , согласно неопубликованному препринту. ^[8]

семейства множеств с короткой цепью не более 3 или длинной цепью не менее n-1: ^[9]

В ноябре 2022 года был опубликован препринт, подтверждающий следующее утверждение: ^[10]^[11]

Для каждого семейства, замкнутого объединением, кроме семейства, содержащего только пустое множество, существует элемент, который принадлежит хотя бы части 0,01 множеств в семействе.

в доказательстве использовались вероятностные Для получения такой оценки и энтропийные методы. Гипотеза в этой статье подразумевала возможное улучшение нижней границы доли $(3-{\sqrt {5}}\,)/2\approx 0.38197$ . Сама гипотеза о замкнутых множествах соответствует дроби $0.5$ .

Через несколько дней были опубликованы три препринта, в которых была установлена нижняя граница доли $(3-{\sqrt {5}}\,)/2$ . ^[12] Вскоре за ними последовали еще два препринта, в которых нижняя граница была увеличена до $0.38234$ . ^[13]^[14]

История

Петер Франкл сформулировал эту гипотезу в терминах семейств множеств с замкнутыми пересечениями в 1979 году, поэтому эту гипотезу обычно приписывают ему и иногда называют гипотезой Франкла . Самая ранняя публикация версии гипотезы о закрытом союзе принадлежит Даффусу (1985) . История работы над гипотезой до 2013 года была опубликована Bruhn & Schaudt (2015) .

Примечания

^ Тимоти Гауэрс, Твит от 17 ноября 2022 г.
^ Брюн и Шаудт (2015)
^ Абэ (2000) ; Пунен (1992) ; Рейнхольд (2000)
^ Брюн и др. (2015) .
^ Робертс и Симпсон (2010) .
^ Бошняк и Маркович (2008) , улучшение предыдущих оценок Морриса (2006) , Ло Фаро (1994) и других.
^ Sarvate & Renaud (1989) , с тех пор заново открыт несколькими другими авторами. Если существует одно- или двухэлементное множество S , некоторый элемент S принадлежит по крайней мере половине множеств в семействе, но это же свойство не выполняется для трехэлементных множеств из-за контрпримеров Сарвате, Рено и Рональд Грэм .
^ Карпас (2017) .
^ Тиан (2021)
^ Гилмер (2022)
^ «Программист с искусственным интеллектом, давно не знакомый с математикой, решает чисто математическую задачу» . Журнал Кванта . 03.01.2023 . Проверено 03 января 2023 г.
^ Чейз и Ловетт (2022) ; Алвейс, Хуан и Селлке (2022) ; Савин (2022)
^ Yu (2022)
^ Изменение (2022)

Ссылки

Абэ, Тецуя (2000). «Сильные полумодулярные решетки и гипотеза Франкла». Алгебра Универсалис . 44 (3–4): 379–382. дои : 10.1007/s000120050195 . S2CID 120741780 .
Алвейс, Райан; Хуанг, Брайс; Селлке, Марк (21 ноября 2022 г.). «Улучшенная нижняя граница гипотезы о замкнутых множествах». arXiv : 2211.11731 [ math.CO ].
Бошняк, Ивица; Маркович, Питер (2008). «11-элементный случай гипотезы Франкла» . Электронный журнал комбинаторики . 15 (1): R88. дои : 10.37236/812 .
Брюн, Хеннинг; Шарби, Пьер; Шаудт, Оливер; Телле, Ян Арне (2015). «Графовая формулировка гипотезы об объединенно-замкнутых множествах». Европейский журнал комбинаторики . 43 : 210–219. arXiv : 1212.4175 . дои : 10.1016/j.ejc.2014.08.030 . МР 3266293 . S2CID 2373192 .
Брюн, Хеннинг; Шаудт, Оливер (01 ноября 2015 г.). «Путешествие гипотезы о замкнутых множествах» . Графы и комбинаторика . 31 (6): 2043–2074. arXiv : 1309.3297 . дои : 10.1007/s00373-014-1515-0 .
Чейз, Закари; Ловетт, Шачар (21 ноября 2022 г.). «Приближенная гипотеза о закрытом союзе». arXiv : 2211.11689 [ math.CO ].
Камби, Стейн (23 декабря 2022 г.). «Лучшие оценки гипотезы о множествах, замкнутых объединением, с использованием энтропийного подхода». arXiv : 2212.12500 [ math.CO ].
Даффус, Д. (1985). Соперник, И. (ред.). Открыть проблемный сеанс . Графики и порядок. Д. Рейдель. п. 525.
Гилмер, Джастин (16 ноября 2022 г.). «Постоянная нижняя оценка гипотезы о множествах, замкнутых в объединении». arXiv : 2211.09055 [ math.CO ].
Карпас, Илан (2017). «Два результата о семьях, состоящих из союзов». arXiv : 1708.01434 [ math.CO ].
Тянь, Чэньсяо (2021). «Гипотеза о замкнутых множествах верна для высоты H(𝓕)≤ 𝟑 и H(𝓕)≥ 𝐧 - 𝟏». arXiv : 2112.06659 [ math.CO ].
Ло Фаро, Джованни (1994). «Гипотеза о замкнутых множествах: улучшенные границы». Дж. Комбин. Математика. Комбинировать. Вычислить . 16 : 97–102. МР 1301213 .
Моррис, Роберт (2006). «FC-семейства и улучшенные оценки гипотезы Франкла». Европейский журнал комбинаторики . 27 (2): 269–282. arXiv : math/0702348 . дои : 10.1016/j.ejc.2004.07.012 . МР 2199779 . S2CID 17633023 .
Пунен, Бьорн (1992). «Союзно-замкнутые семьи» . Журнал комбинаторной теории . Серия А. 59 (2): 253–268. дои : 10.1016/0097-3165(92)90068-6 . МР 1149898 .
Рейнхольд, Юрген (2000). «Гипотеза Франкла верна для нижних полумодулярных решеток». Графы и комбинаторика . 16 (1): 115–116. дои : 10.1007/s003730050008 . S2CID 12660895 .
Робертс, Ян; Симпсон, Джейми (2010). «Заметка о гипотезе о множествах, замкнутых в объединении» (PDF) . Австралия. Дж. Комбин . 47 : 265–267.
Сарвате, генеральный директор; Рено, Ж.-К. (1989). «О гипотезе об объединенно-замкнутых множествах». Арс Комбин . 27 : 149–153. МР 0989460 .
Савин, Уилл (21 ноября 2022 г.). «Улучшенная нижняя оценка гипотезы о замкнутом множестве». arXiv : 2211.11504 [ math.CO ].
Ю, Лей (01 декабря 2022 г.). «Гипотеза о безразмерных границах для гипотезы о замкнутых множествах». arXiv : 2212.00658 [ math.CO ].

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

Гипотеза Франкла о замкнутых множествах , «Сад открытых проблем».
Гипотеза о замкнутых множествах (1979) . В книге «Открытые проблемы – теория графов и комбинаторика» , собранной DB West.

[1] Тимоти Гауэрс, Твит от 17 ноября 2022 г.

[2] Брюн и Шаудт (2015)

[3] Абэ (2000) ; Пунен (1992) ; Рейнхольд (2000)

[FOOTNOTEBruhnCharbitSchaudtTelle2015-4] Брюн и др. (2015) .

[FOOTNOTERobertsSimpson2010-5] Робертс и Симпсон (2010) .

[6] Бошняк и Маркович (2008) , улучшение предыдущих оценок Морриса (2006) , Ло Фаро (1994) и других.

[7] Sarvate & Renaud (1989) , с тех пор заново открыт несколькими другими авторами. Если существует одно- или двухэлементное множество S , некоторый элемент S принадлежит по крайней мере половине множеств в семействе, но это же свойство не выполняется для трехэлементных множеств из-за контрпримеров Сарвате, Рено и Рональд Грэм .

[FOOTNOTEKarpas2017-8] Карпас (2017) .

[9] Тиан (2021)

[10] Гилмер (2022)

[11] «Программист с искусственным интеллектом, давно не знакомый с математикой, решает чисто математическую задачу» . Журнал Кванта . 03.01.2023 . Проверено 03 января 2023 г.

[12] Чейз и Ловетт (2022) ; Алвейс, Хуан и Селлке (2022) ; Савин (2022)

[13] Yu (2022)

[14] Изменение (2022)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]