[#P41] Union-closed sets conjecture
Problem. If \(\mathcal{F}\) is a finite nonempty family of finite sets satisfying \(A\cup B\in\mathcal{F}\) for all \(A,B\in\mathcal{F}\), then some element belongs to at least \(|\mathcal{F}|/2\) members of \(\mathcal{F}\).
1Context
The conjecture, also called Frankl's conjecture, asks whether closure under union forces one element to appear with frequency at least one half.
2Problem setup
Definition 1 (A family). A family is union-closed when the union of any two member sets is also a member.
Definition 2 (The frequency of an element). The frequency of an element is the number of member sets containing it.
Remark 1. The conjecture, also called Frankl's conjecture, asks whether closure under union forces one element to appear with frequency at least one half.
3What counts as a solution
- Prove the half-frequency conclusion for every qualifying finite family, or give a finite union-closed family and prove that each element occurs in fewer than half of its sets.
1Status
Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: Gilmer proved the first constant 0.01. Subsequent entropy work gives an unconditional constant about 0.38234. A reported 0.38271 relies on numerically verified hypotheses. Exact unresolved remainder: Prove half-frequency for every qualifying finite union-closed family, or certify a counterexample.[1][2][3]
1Records
Notes and companion material
Original intake status. The cited 2024 paper identifies the union-closed sets conjecture as open. The source and public status were checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.
- Strong asymptotic lower bounds and many finite or structural cases are known, while the one-half threshold remains open.
Recorded example 1. For the family {empty set, {1}, {1,2}}, the element 1 appears in two of the three sets.
Computational notes
- Exhaustive family generation can verify bounded universe or family sizes only.
2See also
- Cycle Double Cover Conjecturecombinatorics
- The Total Coloring Conjecturecombinatorics
- Sabidussi's Compatibility Conjecturecombinatorics
How to cite
TheoremDB contributors, “Union-closed sets conjecture,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/union-closed-sets-conjectureThis page as plain text: union-closed-sets-conjecture.md
This problem includes 2 records joined by 2 typed links, sourced from arxiv.org[1], current as of July 31, 2026.
1References
- Packet source. Kengbo Lu and Abigail Raz, “Note on the union-closed sets conjecture and Reimer's average set size theorem”. arXiv:2405.10639 (2024). arXiv:2405.10639, abstract and introduction. ↗preprint · primary source · arXiv:2405.10639, checked 2026-07-31 · checked 2026-07-31Source use: original summary.The cited 2024 paper identifies the union-closed sets conjecture as open. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at Abstract and introduction.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.Packet-linked open-status source.Source named by the research packet.
- Justin Gilmer, “A constant lower bound for the union-closed sets conjecture”. arXiv:2211.09055 (2022). Abstract. ↗preprint · primary source · arXiv:2211.09055v2 · checked 2026-08-01Source use: original summary.First universal constant lower bound.
- Lei Yu, “Dimension-Free Bounds for the Union-Closed Sets Conjecture”. Entropy 25(5) (2023), 767. DOI 10.3390/e25050767. Abstract. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Computable entropy bound evaluated at approximately 0.38234.
An original CC0 restatement prepared by TheoremDB maintainers.