Гипотеза о замкнутых множествах - Union-closed sets conjecture - Wikipedia

Нерешенная проблема в математике:

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

(больше нерешенных задач по математике)

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

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

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

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

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

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

Известно, что семьи удовлетворяют гипотезе

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

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

История

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

Примечания

^ Эйб (2000); Пунен (1992); Райнхольд (2000)
^ Bruhn et al. (2015).
^ Робертс и Симпсон (2010).
^ Бошняк и Маркович (2008), улучшая предыдущие оценки на Моррис (2006), Ло Фаро (1994) и другие.
^ Сарват и Рено (1989), так как был переоткрыт несколькими другими авторами. Если одноэлементный или двухэлементный набор S существует, некоторый элемент S принадлежит по крайней мере к половине наборов в семействе, но это же свойство не выполняется для трехэлементных наборов из-за контрпримеров Сарвата, Рено и Рональд Грэм.
^ Карпас (2017).

внешняя ссылка

Гипотеза Франкла о объединяемых замкнутых множествах, Открытый Проблемный Сад.
Гипотеза о замкнутых наборах (1979). В Открытые задачи - теория графов и комбинаторика, собранные Д. Б. Вестом.
Вайсштейн, Эрик В. «Гипотеза о замкнутых множествах». MathWorld.

[1] Эйб (2000); Пунен (1992); Райнхольд (2000)

[FOOTNOTEBruhnCharbitSchaudtTelle2015-2] Bruhn et al. (2015).

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]