Problem Statement
How large can a union-free collection $\mathcal{F}$ of subsets of $[n]$ be? By union-free we mean there are no solutions to $A\cup B=C$ with distinct $A,B,C\in \mathcal{F}$. Must $\lvert \mathcal{F}\rvert =o(2^n)$? Perhaps even\[\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}?\]
Categories:
Combinatorics
Progress
The estimate $\lvert \mathcal{F}\rvert=o(2^n)$ implies that if $A\subset \mathbb{N}$ is a set of positive density then there are infinitely many distinct $a,b,c\in A$ such that $[a,b]=c$ (i.e. [487]).In [Er65b] Erdős reported that the estimate $\lvert \mathcal{F}\rvert=o(2^n)$ was proved in unpublished work by Sárközy and Szemerédi.
Solved by Kleitman [Kl71], who proved\[\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}.\]If we forbid the union of any number of sets in $\mathcal{F}$ being in the family then this is the subject of [1023].
Source: erdosproblems.com/447 | Last verified: January 15, 2026