Erdős problem 447 · problems.science

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}$ . Perhaps even $\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}?$

Sources

Browse retained paths and inspect the exact material available for this Problem.

2 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

447.lean

Retained formal statement2 of 2

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

FormalConjectures/ErdosProblems/447.leanErdos447.erdos_447.parts.ii2 linesExact file

1True ↔2  ∃ 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.

Sources

Search problems.science