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

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

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

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

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

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

• Гипотеза верна для семейств из не более чем 46 множеств .
• Гипотеза верна для семейств множеств из не более чем 11 элементов .
• Гипотеза верна для семейств множеств, в которой самое маленькое множество имеет один или два элемента , since rediscovered by several other authors. If a one-element or two-element set S exists, some element of S belongs to at least half the sets in the family, but the same property does not hold for three-element sets, due to counterexamples of Sarvate, Renaud, and Ronald Graham .</ref>.
• Для некоторой постоянной ${\displaystyle \varepsilon >0}$ , гипотеза верна для по крайней мере ${\displaystyle ({\tfrac {1}{2}}-\varepsilon ){\cdot }2^{n}}$ различных семейств подмножеств из ${\displaystyle n}$ -элементного множества .

История

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

Примечания

Литература

• Abe, Tetsuya (2000). "Strong semimodular lattices and Frankl's conjecture". Algebra Universalis . 44 (3—4): 379—382. doi : . S2CID .
• Alweiss, Ryan; Huang, Brice; Sellke, Mark (2022-11-21). "Improved Lower Bound for the Union-Closed Sets Conjecture". arXiv : [ ].
• Bošnjak, Ivica; Marković, Peter (2008). . . 15 (1): R88. doi : .
• Bruhn, Henning; Charbit, Pierre; Schaudt, Oliver; Telle, Jan Arne (2015). "The graph formulation of the union-closed sets conjecture". . 43 : 210—219. arXiv : . doi : . MR . S2CID .
• Bruhn, Henning; Schaudt, Oliver (2015-11-01). . Graphs and Combinatorics (англ.) . 31 (6): 2043—2074. arXiv : . doi : .
• Chase, Zachary; Lovett, Shachar (2022-11-21). "Approximate union closed conjecture". arXiv : [ ].
• Cambie, Stijn (2022-12-23). "Better bounds for the union-closed sets conjecture using the entropy approach". arXiv : [ ].
• (1985). (ed.). Open problem session . Graphs and Order. D. Reidel. p. 525.
• Gilmer, Justin (2022-11-16). "A constant lower bound for the union-closed sets conjecture". arXiv : [ ].
• Karpas, Ilan (2017). "Two Results on Union-Closed Families". arXiv : [ ].
• Lo Faro, Giovanni (1994). "Union-closed sets conjecture: improved bounds". J. Combin. Math. Combin. Comput . 16 : 97—102. MR .
• (2006). "FC-families and improved bounds for Frankl's conjecture". . 27 (2): 269—282. arXiv : . doi : . MR . S2CID .
• (1992). . Journal of Combinatorial Theory . Series A. 59 (2): 253—268. doi : . MR .
• Reinhold, Jürgen (2000). "Frankl's conjecture is true for lower semimodular lattices". . 16 (1): 115—116. doi : . S2CID .
• Roberts, Ian; Simpson, Jamie (2010). (PDF) . Australas. J. Combin . 47 : 265—267.
• Sarvate, D. G.; Renaud, J.-C. (1989). "On the union-closed sets conjecture". Ars Combin . 27 : 149—153. MR .
• (2022-11-21). "An improved lower bound for the union-closed set conjecture". arXiv : [ ].
• Yu, Lei (2022-12-01). "Dimension-Free Bounds for the Union-Closed Sets Conjecture". arXiv : [ ].