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 statement1 of 2

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)$ ?

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.

FormalConjectures/ErdosProblems/447.leanErdos447.erdos_447.parts.i1 lineExact file

1True ↔ (fun n => ↑(Erdos447.maxUnionFree n)) =o[Filter.atTop] fun n => 2 ^ n

SolvedStatement only, no proof

Sources

Search problems.science