Combinatorics Extremal combinatorics Conjecture

Union-closed sets conjecture

Statement

Let $\mathcal{F}$ be a finite family of finite sets that contains at least one nonempty set. Suppose that $\mathcal{F}$ is union-closed: $A \cup B \in \mathcal{F}$ for all $A, B \in \mathcal{F}$ , where $\cup$ is the union. Then there is an element $x$ that belongs to at least $|\mathcal{F}| / 2$ of the sets in $\mathcal{F}$ .

Remarks

The conjecture is attributed to Péter Frankl and is also called Frankl's conjecture. It is open. In 2022 Justin Gilmer proved that some element lies in at least $0.01 \, |\mathcal{F}|$ of the sets, the first bound by a positive constant fraction. Several authors then improved the constant to about $0.38$ . The conjecture is known when $\mathcal{F}$ contains a set with one or two elements: such an element, or one of the two elements, works.

Example: $\mathcal{F} = \set{\emptyset, \set{1}, \set{2}, \set{1, 2}}$ is union-closed, and the element $1$ lies in $2 = |\mathcal{F}|/2$ of its sets, so the bound $1/2$ cannot be improved. The nonempty hypothesis is needed: $\mathcal{F} = \set{\emptyset}$ is union-closed, but no element lies in any of its sets.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`4628Z96WVZ`
URI	`m2://4628Z96WVZ`
Kind	conjecture
Writing	W0 stub
MSC	05D05
Status	This copy of the site has no build data. Run `m2 status 4628Z96WVZ`.
About	Family of sets
Uses	Family of sets, Union
Same as	Wikidata Q2993338 Wikipedia Union-closed sets conjecture

Union-closed sets conjecture

Statement

Remarks

Reading path

Further reading

What this page needs for W1

What links here