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 statement1 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}. Must ∣F∣=o(2n)\lvert \mathcal{F}\rvert =o(2^n)?

In [Er65b] Erdős reported that the estimate ∣F∣=o(2n)\lvert \mathcal{F}\rvert=o(2^n) was proved in unpublished work by Sárközy and Szemerédi.

FormalConjectures/ErdosProblems/447.leanErdos447.erdos_447.parts.i1 lineExact file
True ↔ (fun n => ↑(Erdos447.maxUnionFree n)) =o[Filter.atTop] fun n => 2 ^ n
SolvedStatement only, no proof