OP-0009Partially solvedCombinatorics

Frankl's union-closed sets conjecture

In any finite union-closed family, must some element lie in at least half the sets?

Inferred from the community field; finer classification has not been reviewed.

Read original source ↗ 0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

A finite family $\mathcal{F}$ of finite sets is union-closed if $A, B \in \mathcal{F}$ implies $A\cup B \in \mathcal{F}$ . Conjecture: if $\mathcal{F}$ is union-closed and contains a non-empty set, then some element belongs to at least $|\mathcal{F}|/2$ of the members of $\mathcal{F}$ .

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

Attributed to Péter Frankl in 1979. For four decades no constant $c>0$ was known for which some element appears in a $c$ fraction of the sets, despite the statement being accessible to an undergraduate.

Known partial results

Gilmer (2022) broke the barrier with an entropy argument, obtaining $c \approx 0.01$ .
Within weeks several groups independently improved the constant to $(3-\sqrt5)/2 \approx 0.38$ , which is the natural limit of Gilmer's method.
The gap between $0.38$ and $0.5$ appears to require a genuinely different idea.
The conjecture is known for families with at most a moderate number of sets, and for families containing a singleton or a doubleton.

References

[1]J. Gilmer, A constant lower bound for the union-closed sets conjecture (2022). link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.