Гипотеза Франкла

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

Формулировки

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

На языке теории решёток

В любой конечной решётке существует элемент х, который не соединение двух любых мелких элементов (sic!), такой, что число элементов, больших или равных х, составляет не больше половины решетки, с равенством только в случае, если решетка является булевойШаблон:Sfn. Эта версия гипотезы верна и для нескольких естественных классов решётокШаблон:SfnШаблон:SfnШаблон:Sfn.

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

• Гипотеза верна для семейств из не более чем 46 множествШаблон:Sfnp.
• Гипотеза верна для семейств множеств из не более чем 11 элементовШаблон:SfnШаблон:SfnШаблон:Sfn.
• Гипотеза верна для семейств множеств, в которой самое маленькое множество имеет один или два элементаШаблон:Sfn.
• Для некоторой постоянной $\epsilon >0$, гипотеза верна для по крайней мере $(\frac{1}{2}-\epsilon )\cdot 2^n$ различных семейств подмножеств из $n$-элементного множестваШаблон:Sfnp.

История

Оригинальная формулировка Петера Франкла давалась через семейства замкнутые относительно пересечений. Самое раннее упоминание в печати даётся в 1985 году.Шаблон:Нет АИ

Литература

• Шаблон:Cite journal
• Шаблон:Cite arXiv
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite arXiv
• Шаблон:Cite arXiv
• Шаблон:Cite conference
• Шаблон:Cite arXiv
• Шаблон:Cite arXiv
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite arXiv
• Шаблон:Cite arXiv