Union-closed sets conjecture. Проблемы с пониманием. :)

[Circiter]

Вот привлекла моё внимание одна задачка (см. здесь или здесь) об одном интересном свойстве семейств множеств. Утверждается, что для любого конечного семейства конечных множеств, замкнутого относительно операции объединения (то есть такого, что объединение любых двух множеств семества тоже принадлежит этому семейству) и отличного от семества, состоящего лишь из одного пустого множества, существует элемент, принадлежащий по крайней мере половине множеств из этого семейства.

Пусть $\mathcal{F}$ -- данное семейство. Замкнутость по объединению выглядит как $A,\ B\in\mathcal{F}\Rightarrow A\cup B\in\mathcal{F}$. Среди множеств этого семейства можно выделить $k$ минимальных по включению. Понятно, что все остальные множества семейства получаются путем объединения этих $k$ минимальных во всевозможных комбинациях. Давайте попробуем оценить количества различных комбинаций.

Сопоставим $k$ множествам двоичный вектор-маску длины $k$. Каждый разряд соответствует некоторому множеству, а значение разряда определяет присутствие множества в определенной комбинации (1 -- присутствует, 0 -- нет). Так, например, количество всевозможных комбинаций множеств, за исключением пустой комбинации, равно количеству всевозможных значений маски за исключением значения, состоящего из один нулей, то есть $2^k-1$. Собственно, именно этому числу должна быть равна мощность семейства, $|\mathcal{F}|=2^k-1$.

Теперь выберем одно из $k$ минимальных множеств и подсчитаем количество комбинаций его со всеми остальными множествами. Набор этих комбинаций, очевидно, является подсемейством $\mathcal{F}$, обозначим его $\mathcal{M}\subseteq\mathcal{F}$. После фиксации одного бита маски становится видно, что всего таких комбинаций существует $|\mathcal{M}|=2^{k-1}$. Так как выбранное множество гарантированно входит в каждую из комбинаций, то пересечение этих комбинаций равно выбранному множеству, то есть не пусто:

$$\bigcap_{m\in\mathcal{M}}m\neq\varnothing.$$

Сравним мощности $\mathcal{F}$ и $\mathcal{M}$:

$$\frac{2^k-1}{2^{k-1}}=2-\frac{1}{2^{k-1}}\ \Rightarrow\ \frac{2^k-1}{2^{k-1}}<2\ \Rightarrow\ 2|\mathcal{M}|>|\mathcal{F}|.$$

Итак, теперь мы знаем, что у семейства, замкнутого относительно объединения, существует подсемейство с мощностью не менее половины мощности всего семейства и пересечение всех множеств этого подсемейства не пусто. Но ведь это ровно и означает, что существует элемент, принадлежащий не менее чем половине множеств из $\mathcal{F}$...

Однако, исходная гипотеза считается открытой проблемой и новые результаты поступают чрезвычайно редко и по чайное ложке. К примеру, справедливость гипотезы на данный момент установлена лишь для семейств, содержащих не более тридцати шести (или сорока, точно не знаю) множеств; для семейств, объединение множеств которых содержит не более одиннадцати элементов; и для семейств, самые маленькие (по мощности) множества которых имеют не более двух элементов.

Так в чем же заключается сложность этой гипотезы? Что-то до меня не доходит... :) Надеюсь на ваши комментарии... Спасибо.

[Dandan]

Circiter в сообщении #345586 писал(а):

Понятно, что все остальные множества семейства получаются путем объединения этих $k$ минимальных во всевозможных комбинациях.

это неверно. F = { {1}, {1,2} }.

[hurtsy]

Dandan в сообщении #345657 писал(а):

это неверно. F = { {1}, {1,2} }.

Имхо, множества в задаче являются заданными априори. Операция которую Вы применили не является обединением множеств. Пеано, подобным образом, использовал пустое множество. В результате получается незамкнутое(бесконечное) множество. С уважением,