Введение
Предположение 1979 года в комбинаторике
Предположение о союзно замкнутых множествах, также известное как предположение Франкла, — это нерешённая проблема в комбинаторике, сформулированная Петером Франклом в 1979 году. Семейство множеств называется союзно замкнутым, если объединение любых двух множеств из этого семейства принадлежит самому семейству. Предположение утверждает: для любого конечного союзно замкнутого семейства множеств, за исключением семейства, содержащего только пустое множество, существует элемент, принадлежащий по крайней мере половине множеств в семействе. Профессор Тимоти Говерс назвал это «одной из наиболее известных открытых проблем в комбинаторике» и отметил, что предположение «кажется таким, которое должно быть простым в доказательстве (и в результате привлекло множество ошибочных доказательств за эти годы). Хороший способ понять, почему это не так просто, — потратить день на попытки его доказать. Та хитрая идея с усреднением, которая у вас была, не сработает».
Основные результаты
Легко показать, что если союзно-замкнутое семейство содержит одиночный элемент (как в примере выше), то этот элемент должен встречаться по крайней мере в половине множеств семейства. Если существует контрпример к гипотезе, то существует и контрпример, состоящий только из конечных множеств. Поэтому, без ограничения общности, будем считать, что все множества в данном союзно-замкнутом семействе конечны. Для любого конечного непустого множества, множество всех его подмножеств, то есть множество степеней, является союзно-замкнутым. Каждый элемент этого множества содержится ровно в половине его подмножеств. Следовательно, в общем случае нельзя требовать, чтобы элемент содержался более чем в половине множеств семейства: оценка в гипотезе является точной.
Формулировка пересечения
Предположение о союзном замкнутом множестве верно тогда и только тогда, когда система множеств, замкнутая относительно пересечений, содержит элемент не более чем в половине множеств из , где – универсальное множество, то есть объединение всех членов системы . Следующие факты демонстрируют эквивалентность. Во-первых, мы покажем, что система множеств является союзно замкнутой тогда и только тогда, когда её дополнение замкнуто относительно пересечений. Лемма 1. Если – союзно замкнутое семейство множеств с универсальным множеством , то семейство дополнений множеств из замкнуто относительно пересечений. Доказательство. Мы определяем дополнение к системе множеств как
The following facts show the equivalence. Firstly, we show that a set system is union closed if and only if its complement is intersection closed. Lemma 1. If is a union closed family of sets with universe , the family of complement sets to sets in is closed under intersection. Proof. We define the complement of the set system as
Let , be arbitrary sets in and so and are both in Since is union closed, is in , and therefore the complement of , is in , the elements in neither , nor
And this is exactly the intersection of the complements of and , Therefore, is union closed if and only if the complement of , is intersection closed. Secondly, we show that if a set system contains an element in at least half the sets, then its complement has an element in at most half. Lemma 2. A set system contains an element in half of its sets if and only if the complement set system , contains an element in at most half of its sets. Proof. Trivial. Therefore, if is a union closed family of sets, the family of complement sets to sets in relative to the universe is closed under intersection, and an element that belongs to at least half of the sets of belongs to at most half of the complement sets. Thus, an equivalent form of the conjecture (the form in which it was originally stated) is that, for any intersection closed family of sets that contains more than one set, there exists an element that belongs to at most half of the sets in the family.
Пусть , – произвольные множества из , следовательно, и оба принадлежат . Поскольку – союзно замкнутое, то – принадлежит , и, следовательно, дополнение к , – принадлежит , элементы не принадлежат ни , ни .
The following facts show the equivalence. Firstly, we show that a set system is union closed if and only if its complement is intersection closed. Lemma 1. If is a union closed family of sets with universe , the family of complement sets to sets in is closed under intersection. Proof. We define the complement of the set system as
Let , be arbitrary sets in and so and are both in Since is union closed, is in , and therefore the complement of , is in , the elements in neither , nor
And this is exactly the intersection of the complements of and , Therefore, is union closed if and only if the complement of , is intersection closed. Secondly, we show that if a set system contains an element in at least half the sets, then its complement has an element in at most half. Lemma 2. A set system contains an element in half of its sets if and only if the complement set system , contains an element in at most half of its sets. Proof. Trivial. Therefore, if is a union closed family of sets, the family of complement sets to sets in relative to the universe is closed under intersection, and an element that belongs to at least half of the sets of belongs to at most half of the complement sets. Thus, an equivalent form of the conjecture (the form in which it was originally stated) is that, for any intersection closed family of sets that contains more than one set, there exists an element that belongs to at most half of the sets in the family.
И это как раз пересечение дополнений к и . Таким образом, – союзно замкнутое тогда и только тогда, когда дополнение к , – замкнуто относительно пересечений. Во-вторых, мы покажем, что если система множеств содержит элемент хотя бы в половине множеств, то её дополнение содержит элемент не более чем в половине. Лемма 2. Система множеств содержит элемент в половине своих множеств тогда и только тогда, когда система дополнений содержит элемент не более чем в половине своих множеств. Доказательство. Тривиально. Следовательно, если – союзно замкнутое семейство множеств, то семейство дополнений множеств относительно универсального множества замкнуто относительно пересечений, и элемент, принадлежащий хотя бы половине множеств из , принадлежит не более чем половине дополнений множеств. Таким образом, эквивалентная формулировка гипотезы (в той форме, в которой она была первоначально сформулирована) заключается в том, что для любого семейства множеств, замкнутого относительно пересечений и содержащего более одного множества, существует элемент, принадлежащий не более чем половине множеств в этом семействе.
The following facts show the equivalence. Firstly, we show that a set system is union closed if and only if its complement is intersection closed. Lemma 1. If is a union closed family of sets with universe , the family of complement sets to sets in is closed under intersection. Proof. We define the complement of the set system as
Let , be arbitrary sets in and so and are both in Since is union closed, is in , and therefore the complement of , is in , the elements in neither , nor
And this is exactly the intersection of the complements of and , Therefore, is union closed if and only if the complement of , is intersection closed. Secondly, we show that if a set system contains an element in at least half the sets, then its complement has an element in at most half. Lemma 2. A set system contains an element in half of its sets if and only if the complement set system , contains an element in at most half of its sets. Proof. Trivial. Therefore, if is a union closed family of sets, the family of complement sets to sets in relative to the universe is closed under intersection, and an element that belongs to at least half of the sets of belongs to at most half of the complement sets. Thus, an equivalent form of the conjecture (the form in which it was originally stated) is that, for any intersection closed family of sets that contains more than one set, there exists an element that belongs to at most half of the sets in the family.
Формулировка решетки
Хотя выше это было сказано в терминах семейств множеств, гипотеза Франкла также была сформулирована и изучена как вопрос в теории решёток. Решётка – частично упорядоченное множество, в котором для любых двух элементов x и y существует единственный наибольший элемент, меньший или равный обоим (наименьшая верхняя грань x и y), и единственный наименьший элемент, больший или равный обоим (наибольшая нижняя грань x и y). Семейство всех подмножеств множества S, упорядоченное по включению, образует решётку, в которой наименьшая верхняя грань представлена пересечением множеств, а наибольшая нижняя грань – объединением множеств; решётка, построенная таким образом, называется булевой решёткой. Решёточная формулировка гипотезы Франкла утверждает, что в любой конечной решётке существует элемент x, который не является наибольшей нижней гранью любых двух меньших элементов, и число элементов, больших или равных x, составляет не более половины всех элементов решётки, причем равенство достигается только в случае, когда решётка является булевой. Как показано, это утверждение о решётках эквивалентно гипотезе Франкла для семейств, замкнутых относительно объединения: любую решётку можно преобразовать в семейство, замкнутое относительно объединения, и любое семейство, замкнутое относительно объединения, можно преобразовать в решётку, так что истинность гипотезы Франкла для преобразованного объекта влечёт истинность гипотезы для исходного объекта. Известно, что эта решёточная формулировка гипотезы верна для нескольких естественных подклассов решёток, но в общем случае остаётся нерешённой.
Графо-теоретическая формулировка
Другая эквивалентная формулировка гипотезы о союзе замкнутых множеств использует теорию графов. В неориентированном графе независимым множеством называется набор вершин, никакие две из которых не смежны; независимое множество является максимальным, если оно не является подмножеством большего независимого множества. В любом графе "тяжёлые" вершины, входящие в состав более чем половины максимальных независимых множеств, сами должны образовывать независимое множество. Следовательно, если граф не пуст, всегда существует хотя бы одна нетяжёлая вершина – вершина, входящая в состав не более половины максимальных независимых множеств. Графовая формулировка гипотезы о союзе замкнутых множеств утверждает, что любой конечный непустой граф содержит две смежные нетяжёлые вершины. Это автоматически верно, если граф содержит нечётный цикл, поскольку независимое множество, состоящее из всех тяжёлых вершин, не может покрыть все рёбра цикла. Поэтому более интересным случаем гипотезы является случай двудольных графов, которые не содержат нечётных циклов. Другая эквивалентная формулировка гипотезы заключается в том, что в каждом двудольном графе существуют две вершины, по одной на каждой стороне двудольного разбиения, такие, что каждая из этих двух вершин входит не более чем в половину максимальных независимых множеств графа. Известно, что эта гипотеза верна для хордальных двудольных графов, двудольных графов, являющихся серийно-параллельными, и двудольных графов максимальной степени три.
История
Пётр Франкл сформулировал гипотезу в терминах семейств пересекающихся замкнутых множеств в 1979 году, и поэтому гипотеза обычно приписывается ему и иногда называется гипотезой Франкла. Самая ранняя публикация варианта гипотезы, связанного с объединениями, появилась в работе . История работы над гипотезой до 2013 года была опубликована в .