Problem 447

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}?

Source: erdosproblems.com/447

Combinatorics

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem PROVED (LEAN), crediting Kleitman [Kl71]; the Lean artifact behind the qualifier is described under Formalization. The accepted claim is union-free families have at most (1+o(1)) times the middle layer.

Er61: Erdős, P., Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221-254; section II, item 1. Library home: Erdős 1961.
Er65b: Erdős, Paul, Some recent advances and current problems in number theory. Lectures on Modern Mathematics, Vol. III (1965), 196-244; display (69) on printed p. 228. Library home: Erdős 1965.
Kl71: Kleitman, Daniel, Collections of subsets containing no two sets and their union. Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, 1968), Amer. Math. Soc. (1971), 153-155. Not held here.

Problem 447

Status

Proof claims

Discussion