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

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

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

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

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

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

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

• Гипотеза верна для семейств из не более чем 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>.
• Для некоторой постоянной $\varepsilon >0$, гипотеза верна для по крайней мере $({\tfrac {1}{2}}-\varepsilon ){\cdot }2^{n}$ различных семейств подмножеств из $n$-элементного множества.

История

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

Литература

• Abe, Tetsuya (2000). "Strong semimodular lattices and Frankl's conjecture". Algebra Universalis. 44 (3—4): 379—382. doi:10.1007/s000120050195. S2CID 120741780.
• Alweiss, Ryan; Huang, Brice; Sellke, Mark (2022-11-21). "Improved Lower Bound for the Union-Closed Sets Conjecture". arXiv:2211.11731 [math.CO].
• Bošnjak, Ivica; Marković, Peter (2008). "The 11-element case of Frankl's conjecture". Electronic Journal of Combinatorics. 15 (1): R88. doi:10.37236/812.
• Bruhn, Henning; Charbit, Pierre; Schaudt, Oliver; Telle, Jan Arne (2015). "The graph formulation of the union-closed sets conjecture". European Journal of Combinatorics. 43: 210—219. arXiv:1212.4175. doi:10.1016/j.ejc.2014.08.030. MR 3266293. S2CID 2373192.
• Bruhn, Henning; Schaudt, Oliver (2015-11-01). "The Journey of the Union-Closed Sets Conjecture". Graphs and Combinatorics (англ.). 31 (6): 2043—2074. arXiv:1309.3297. doi:10.1007/s00373-014-1515-0.
• Chase, Zachary; Lovett, Shachar (2022-11-21). "Approximate union closed conjecture". arXiv:2211.11689 [math.CO].
• Cambie, Stijn (2022-12-23). "Better bounds for the union-closed sets conjecture using the entropy approach". arXiv:2212.12500 [math.CO].
• Duffus, D. (1985). Rival, I. (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:2211.09055 [math.CO].
• Karpas, Ilan (2017). "Two Results on Union-Closed Families". arXiv:1708.01434 [math.CO].
• Lo Faro, Giovanni (1994). "Union-closed sets conjecture: improved bounds". J. Combin. Math. Combin. Comput. 16: 97—102. MR 1301213.
• Morris, Robert (2006). "FC-families and improved bounds for Frankl's conjecture". European Journal of Combinatorics. 27 (2): 269—282. arXiv:math/0702348. doi:10.1016/j.ejc.2004.07.012. MR 2199779. S2CID 17633023.
• Poonen, Bjorn (1992). "Union-closed families". Journal of Combinatorial Theory. Series A. 59 (2): 253—268. doi:10.1016/0097-3165(92)90068-6. MR 1149898.
• Reinhold, Jürgen (2000). "Frankl's conjecture is true for lower semimodular lattices". Graphs and Combinatorics. 16 (1): 115—116. doi:10.1007/s003730050008. S2CID 12660895.
• Roberts, Ian; Simpson, Jamie (2010). "A note on the union-closed sets conjecture" (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 0989460.
• Sawin, Will (2022-11-21). "An improved lower bound for the union-closed set conjecture". arXiv:2211.11504 [math.CO].
• Yu, Lei (2022-12-01). "Dimension-Free Bounds for the Union-Closed Sets Conjecture". arXiv:2212.00658 [math.CO].