Skip to content

Erdős problem 447

How large can a union-free collection F\mathcal{F} of subsets of [n][n] be? By union-free we mean there are no solutions to A∪B=CA\cup B=C with distinct A,B,C∈FA,B,C\in \mathcal{F}. Perhaps even ∣F∣<(1+o(1))(n⌊n/2⌋)?\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}?

Sources

The source's own material, retained exactly.

2 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

447.lean

Retained formal statement2 of 2

How large can a union-free collection F\mathcal{F} of subsets of [n][n] be? By union-free we mean there are no solutions to A∪B=CA\cup B=C with distinct A,B,C∈FA,B,C\in \mathcal{F}. Perhaps even ∣F∣<(1+o(1))(n⌊n/2⌋)?\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}?

Solved by Kleitman [Kl71], who proved ∣F∣<(1+o(1))(n⌊n/2⌋).\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}.

FormalConjectures/ErdosProblems/447.leanErdos447.erdos_447.parts.ii2 linesExact file
True ↔  ∃ c, c =o[Filter.atTop] 1 ∧ ∀ᶠ (n : ℕ) in Filter.atTop, ↑(Erdos447.maxUnionFree n) < (1 + c n) * ↑(n.choose (n / 2))
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.