Union-closed sets conjecture
In every finite family of sets that contains the union of any two of its members, does some element belong to at least half of the sets?
Summary
Why it is open
A family of sets is union-closed if the union of any two of its members is also a member. The conjecture says that every finite union-closed family other than {∅}, the family whose only member is the empty set, has an element contained in at least half of its members [1]. It cannot ask for more: in the family of all subsets of a set, every element lies in exactly half [1]. Most authors attribute the conjecture to Péter Frankl and date it to 1979, Henning Bruhn and Oliver Schaudt write, although Balla, Bollobás and Eccles call it a folklore conjecture that "was well known by the mid-1970s" [1]. Frankl formulated it on a journey from Paris to Montreal and told Ron Graham, who spread it [1].
Taking complements turns it into an equivalent statement about intersection-closed families, and it has equivalent forms in lattice theory and graph theory [1]. Bruhn and Schaudt counted about 50 articles dedicated to it [1].
Simone Costa and Ankan Sadhu state the target as a number. Let c be the largest fraction that every such family is guaranteed to reach; the family {∅, {1}} shows that c is at most 1/2, so the conjecture is equivalent to c = 1/2 [11]. A counterexample would be one family in which every element lies in fewer than half the members. Until 2022 no fixed fraction was known: the best general bound, from Knill with an improvement by Wójcik, was of order 1/log₂ n for a family of n sets [2], and Bruhn and Schaudt wrote that even an element in 1% of the sets seemed far from reach [1].
No prize or body sets terms for a resolution. The status here follows Wikipedia's list of unsolved problems in mathematics, which still listed the conjecture on 16 October 2026 [12].
What is known
Special families (before 2022). Call an element abundant if it lies in at least half of the members. Sarvate and Renaud observed that the element of a one-element member is always abundant, and that one of the two elements of a two-element member is; Renaud and Sarvate described a family whose unique smallest member has three elements, none of them abundant [1]. Case analysis by Bošnjak and Marković covered all families on universes of up to 11 elements, and Živković and Vučković, with a computer, extended this to 12; with a lemma of Lo Faro on minimal counterexamples, this gives the conjecture for every family of at most 50 sets [1]. Families with many members also satisfy it: with m elements in the universe, Balla, Bollobás and Eccles proved it for families of at least (2/3)·2^m sets, and Karpas for at least 2^(m−1) [1, 2].
The entropy method (November 2022). On 16 November 2022 Justin Gilmer, of Google Research, posted a preprint proving that some element always lies in at least 1% of the sets: the first constant bound [2]. His key inequality concerns two independent random sets A and B with the same distribution: if every element lies in A with probability at most 0.01, the entropy of A ∪ B, a measure of its uncertainty, is at least 1.26 times that of A [2]. When A and B are drawn uniformly from a union-closed family, A ∪ B stays in the family and cannot have more entropy than A, so some element must be frequent [2]. Gilmer conjectured that the technique could reach (3 − √5)/2 ≈ 0.38 [3, 4]. Three preprints posted on 21 November 2022 proved this independently: by Ryan Alweiss, Brice Huang and Mark Sellke, by Zachary Chase and Shachar Lovett, and by Will Sawin [3, 4, 8, 11]. Alweiss, Huang and Sellke checked one case, a one-variable inequality, by computer; their paper appeared in the Electronic Journal of Combinatorics in 2024 [8]. Chase and Lovett showed that the bound is optimal for approximately union-closed families, in which the unions of nearly all pairs of members belong to the family [3].
Beyond (3 − √5)/2 (2022–2026). Sawin sketched how dependent rather than independent samples give a constant strictly above (3 − √5)/2, and disproved a conjecture of Gilmer that would have implied the full result [4]. In December 2022 Lei Yu made Sawin's improvement computable and evaluated it numerically at about 0.38234 (published in Entropy in 2023) [6], and Stijn Cambie answered Sawin's question exactly, with about 0.3823455, using a computer verification he describes as "slightly less rigorous" than the detailed work for (3 − √5)/2 [7]. In June 2023 Jingbo Liu introduced conditionally independent couplings, improved the bound analytically, and reached about 0.38271 under numerically verified hypotheses [9]. In a preprint first posted on 7 September 2026 and not peer reviewed, Costa and Sadhu prove Liu's threshold of 0.382709087918735 and, with computer-assisted steps, the bound 0.3828852549667978; they also show that the inequality used in their proof cannot give a threshold above 0.3828852599667 [11].
Recent claims. In May 2024 Roberto Demontis posted a preprint claiming a proof of the full conjecture, and a paper with the same title, "The union-closed set conjecture is true", submitted on 1 May 2024, was published in Current Research in Statistics & Mathematics on 11 June 2024 [10]. No published response to it was found when this page was checked; on 16 October 2026 the Wikipedia list still listed the conjecture as unsolved [12].
Main approaches
Entropy inequalities. Compare the entropy of the union of two samples from the family with the entropy of a single sample, choosing how the two samples depend on each other [2, 4, 9]. Strongest evidence: the bounds, from 0.01 in 2022 to 0.3828852549667978 in a 2026 preprint [2, 11]. Main difficulty: (3 − √5)/2 is already optimal for approximately union-closed families [3]; Cambie writes that "another core method will be needed for the full resolution" [7], and Costa and Sadhu prove a ceiling for the inequality they use [11].
Small cases and local configurations. Show that a counterexample must be large, by computer search and by local configurations: small subfamilies, such as a one-element member, whose presence forces an abundant element [1]. Poonen characterised all such configurations by a finite weighting condition [1]. Strongest evidence: the conjecture for universes of up to 12 elements and families of up to 50 sets [1]. Main difficulty: the simple pattern breaks at three-element members, since a smallest member of three elements need not contain an abundant element [1], and David Ellis, Maria-Romina Ivan and Imre Leader built union-closed families whose unique smallest member has no element in more than any given fraction ε of the sets [5].
Large families and averages. If the members contain on average more than half of the universe, some element is abundant; Nishimura and Takahashi used this to prove the conjecture for very large families [1]. Strongest evidence: the thresholds (2/3)·2^m and 2^(m−1) [1, 2]. Main difficulty: "Averaging does not always work", Bruhn and Schaudt write: some union-closed families have average set size and average element frequency too low to deduce the conjecture [1].
Open sub-questions
- Past the entropy ceiling. Is there a coupling outside those Costa and Sadhu combine whose entropy inequality gives a threshold above 0.3828852599667, or does every inequality of this one-coordinate kind stop below 1/2 [7, 11]?
- Checking the 2026 bound. Can the computer-assisted assertions behind 0.3828852549667978, which Costa and Sadhu list in an appendix, be checked independently, for instance in a proof assistant [11]?
- What exact union-closure adds. Since (3 − √5)/2 is optimal for approximately union-closed families, which property of exactly union-closed families do the gains of Sawin, Yu, Cambie and Liu use, and can it be exploited further [3, 4, 6, 7, 9]?
- Beyond 12 elements and 50 sets. Can computer-assisted case analysis verify the conjecture for universes of 13 elements, and with Lo Faro's lemma raise the bound of 50 sets [1]?
- Ellis–Ivan–Leader examples. Do the explicit families containing small sets for which Ellis, Ivan and Leader could not verify the conjecture satisfy it [5]?
- Large families. Can Karpas's threshold of 2^(m−1) members for a universe of m elements be lowered [2]?
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Bruhn, H. & Schaudt, O. (2015). The journey of the union-closed sets conjecture. Graphs and Combinatorics 31(6), 2043–2074. 10.1007/s00373-014-1515-0 · Checked 16 Oct 2026
- Gilmer, J. (2022). A constant lower bound for the union-closed sets conjecture. Preprint, arXiv:2211.09055 (version 2, 28 November 2022; version 1, 16 November 2022), not peer reviewed. Source · Checked 16 Oct 2026
- Chase, Z. & Lovett, S. (2022). Approximate union closed conjecture. Preprint, arXiv:2211.11689 (version 1, 21 November 2022), not peer reviewed. Source · Checked 16 Oct 2026
- Sawin, W. (2022). An improved lower bound for the union-closed set conjecture. Preprint, arXiv:2211.11504 (version 3, 19 June 2023; version 1, 21 November 2022), not peer reviewed. Source · Checked 16 Oct 2026
- Ellis, D., Ivan, M.-R. & Leader, I. (2023). Small sets in union-closed families. The Electronic Journal of Combinatorics 30(1), P1.8. 10.37236/11004 · Checked 16 Oct 2026
- Yu, L. (2023). Dimension-free bounds for the union-closed sets conjecture. Entropy 25(5), 767. 10.3390/e25050767 · Checked 16 Oct 2026
- Cambie, S. (2022). Better bounds for the union-closed sets conjecture using the entropy approach. Preprint, arXiv:2212.12500 (version 2, 16 February 2025; version 1, 23 December 2022), not peer reviewed. Source · Checked 16 Oct 2026
- Alweiss, R., Huang, B. & Sellke, M. (2024). Improved lower bound for Frankl’s union-closed sets conjecture. The Electronic Journal of Combinatorics 31(3), P3.35. 10.37236/12232 · Checked 16 Oct 2026
- Liu, J. (2024). Improving the lower bound for the union-closed sets conjecture via conditionally IID coupling. In 2024 58th Annual Conference on Information Sciences and Systems (CISS), 1–6. 10.1109/ciss59072.2024.10480167 · Checked 16 Oct 2026
- Demontis, R. (2024). The union-closed set conjecture is true. Current Research in Statistics & Mathematics 3(2), 01–07. 10.33140/crsm.03.02.04 · Checked 16 Oct 2026
- Costa, S. & Sadhu, A. (2026). Beyond Liu’s 0.382709 threshold for the union-closed sets conjecture. Preprint, arXiv:2610.02295 (version 1, 1 October 2026; first posted on Zenodo on 7 September 2026, according to the arXiv comment), not peer reviewed. Source · Checked 16 Oct 2026
- Wikipedia. List of unsolved problems in mathematics (revision of 15 October 2026). Source · Checked 16 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 08 Oct 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.