Гипотеза Франкла — гипотеза в комбинаторике, известная как открытая задача с элементарной формулировкой.
Формулировки
Для любого конечного семейства множеств, замкнутого относительно объединения и содержащего непустое множество, найдётся элемент, принадлежащий хотя бы половине множеств из семейства.
На языке теории решёток В любой конечной решётке существует элемент х, который не соединение двух любых мелких элементов (sic!), такой, что число элементов, больших или равных х, составляет не больше половины решетки, с равенством только в случае, если решетка является булевой. Эта версия гипотезы верна и для нескольких естественных классов решёток.
Частичные результаты
Гипотеза верна для семейств из не более чем 46 множеств. Гипотеза верна для семейств множеств из не более чем 11 элементов. Гипотеза верна для семейств множеств, в которой самое маленькое множество имеет один или два элемента. Для некоторой постоянной , гипотеза верна для по крайней мере различных семейств подмножеств из -элементного множества.
История Оригинальная формулировка Петера Франкла давалась через семейства замкнутые относительно пересечений. Самое раннее упоминание в печати даётся в 1985 году.
Примечания
Литература
Категория:Теория решёток Категория:Математические гипотезы Категория:Семейства множеств Категория:Открытые математические проблемы