MathDB

union-closed sets conjecture

About 47 years old · traced to

Let F\mathcal{F} be a finite family of distinct finite sets that is union-closed, i.e.

A,B∈F ⟹ A∪B∈F,A,B\in\mathcal{F}\ \Longrightarrow\ A\cup B\in\mathcal{F},

and suppose F≠∅\mathcal{F}\neq\varnothing and F≠{∅}\mathcal{F}\neq\{\varnothing\}. For an element xx of the ground set U(F)=⋃A∈FAU(\mathcal{F})=\bigcup_{A\in\mathcal{F}}A, put

d(x)=#{A∈F : x∈A}.d(x)=\#\{A\in\mathcal{F}\ :\ x\in A\}.

Then there exists x∈U(F)x\in U(\mathcal{F}) with

d(x) ≥ 12 ∣F∣.d(x)\ \ge\ \tfrac{1}{2}\,|\mathcal{F}|.
Equivalent formulations 2Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. union-closed sets conjecture

    The union-closed sets conjecture, also known as Frankl’s conjecture, is an open problem in combinatorics posed by Péter Frankl in 1979. A family of sets is said to be union-closed if the union of any two sets from the family belongs to the family. The conjecture states: For every finite union-closed family of sets, other than the empty family, there exists an element that belongs to at least half of the sets in the family.

    source: Wikipedia

  2. The Union Closed Sets Conjecture

    Let n∈Nn\in\mathbb{N}, let [n]={1,…,n}[n]=\{1,\dots,n\}, and let P(n)=P([n])\mathcal{P}(n)=\mathcal{P}([n]) be the power set of [n][n]. A family F⊆P(n)\mathcal{F}\subseteq\mathcal{P}(n) is nontrivial when

    ⋃F=[n],\bigcup\mathcal{F}=[n],

    and it is union closed when A,B∈FA,B\in\mathcal{F} implies A∪B∈FA\cup B\in\mathcal{F}. The Union Closed Sets Conjecture. For every nontrivial, union closed F⊆P(n)\mathcal{F}\subseteq\mathcal{P}(n) there is an x∈[n]x\in[n] with

    #{F∈F:x∈F}≥12⋅#F.\#\{F\in\mathcal{F}:x\in F\}\geq\frac{1}{2}\cdot\#\mathcal{F}.

    This conjecture asserts that some element belongs to at least half of the sets in every finite nontrivial union-closed family. It remains open and is a central problem in extremal set theory; the paper studies element frequencies and related structures, including weakenings and generalizations.

    source: Nicolas Nagel, “Notes on the Union Closed Sets Conjecture”, arXiv:2208.03803 (2023).

References

Primary source

Wikipedia

Additional references

  1. Wikipedia, Union-closed sets conjecture, the article this problem comes from.
combinatoricsunsolved-problem
Posted · edited

Progress summary

Refreshed
Claimed progress

The conjecture remains unproved: recent work slightly improves the best partial bound, while a separate complete-proof claim is unverified.

Péter Frankl formally posed the conjecture in 1979: every nontrivial finite union-closed family has an element appearing in at least half its sets.

Known results and August–September 2026 developments

  • Knill (1994) obtained a bound of at least n−1log⁡2n\frac{n-1}{\log_2 n} occurrences; Gilmer (2022) improved this to 1%1\%.
  • Chase, Lovett, Sawin, and Pebody (2022) reached 3−52≈0.381966\frac{3-\sqrt{5}}{2}\approx0.381966; later work reports 0.382710.38271 and, in a September 10, 2026 announcement, 0.382840.38284.
  • An August 2026 preprint proves the conjecture through height 44 and gives reductions at height 55, explicitly leaving the remaining case unresolved.
  • A May 2024 preprint and an August 27, 2026 announcement claim complete proofs, but these claims are unverified.

Community submission (unverified)

Posted September 5, 2026, a submitted argument claims sharp lower bounds of 1919, 2727, 2828, and 3636 when a smallest nonempty member has size 33, under four parity and empty-set conditions. It explicitly does not resolve the conjecture; its Lean verification and novelty are unverified.

Current status (as of September 2026): established results give only sub-50%50\% abundance bounds and restricted cases; a complete proof is claimed but unverified, while the height-five case remains unresolved in the cited preprint.

Sources

Solutions 1

With ChatGPT's assistance, I investigated rare minimal triples in union-closed families. We obtained sharp size bounds: 19 with the empty set and 27 without it, for even-sized families, 28 and 36, respectively. Lean verified the lower-bound proofs. This does not resolve Frankl's conjecture, and novelty remains unconfirmed. I will attach the full report below for independent review and help identifying prior results.See full solutionHide full solution

Partial results on rare elements in a smallest nonempty member

This submission presents partial results concerning union-closed families. The investigation was carried out with assistance from ChatGPT and includes formal verification in Lean. It does not resolve Frankl’s conjecture.

Let F be a union-closed family of subsets of a finite ground set, and let M = |F|. Suppose that S = {a, b, c} belongs to F and has minimum cardinality among the nonempty members of F.

For each element x, define its frequency by

f(x) = |{A ∈ F : x ∈ A}|.

Assume that every element of S is strictly rare:

2f(x) < M for every x ∈ S.

Under these hypotheses, the following bounds are sharp:

• If ∅ ∈ F and M is odd, then M ≥ 19.
• If ∅ ∉ F and M is odd, then M ≥ 27.
• If ∅ ∈ F and M is even, then M ≥ 28.
• If ∅ ∉ F and M is even, then M ≥ 36.

Proof outline

The proof analyzes fibers according to the elements outside S. Under the stated hypotheses, it establishes:

3 · (f(a) + f(b) + f(c)) ≥ 4M + 5 when ∅ ∈ F.

3 · (f(a) + f(b) + f(c)) ≥ 4M + 9 when ∅ ∉ F.

Strict rarity and integrality give:

• f(x) ≤ (M − 1)/2 when M is odd.
• f(x) ≤ M/2 − 1 when M is even.

Combining these inequalities gives the four lower bounds. Explicit union-closed families attain them.

Verification and scope

The lower-bound proofs were revalidated with Lean 4.33.1. The attaining examples were checked separately. The precise scope of formal verification is documented in the attached report.

These examples have abundant elements outside S. They demonstrate failure of abundance within S and are not counterexamples to Frankl’s conjecture.

The 19-member construction has a published antecedent in Rein van der Hout and Kees Roos, “Some results and conjectures related to Frankl’s union closed conjecture”, Journal of Applied and Numerical Optimization 8(1) (2026), 11–18, Section 4, Figure 1.

DOI: 10.23952/jano.8.2026.1.02

Novelty of the additional refinements has not been established.

Attached documents

  1. Main Investigation: statements, arguments, experiments, bibliography, and limitations.
  2. Original Appendices: source listings, historical verification records, and the original source archive.
  3. Lean 4.33.1 Update: revalidation details and the updated source package.

I welcome independent review of the mathematical arguments, the formalization, and the relationship to previously published results.

  • Frankl_Part_1_Main_Investigation.pdf485,738 bytesOpen
  • Frankl_Part_3_Lean_4.33.1_Update.pdf8,802,890 bytesOpen
  • Frankl_Part_2_Original_Appendices.pdf3,628,561 bytesOpen
0
João Pacheco Posted