PROVED
This has been solved in the affirmative.
Let $c>0$, and let $n$ be sufficiently large depending on $c$. Suppose that $\mathcal{F}$ is a family of at most $c2^n$ many finite sets of size $n$. Let $X=\cup_{A\in \mathcal{F}}A$.
Must there exist $\gg_c 2^{\lvert X\rvert}$ many sets $B\subset X$ which intersect every set in $\mathcal{F}$, yet contain none of them?
The existence of a single such $B$ is equivalent to $\mathcal{F}$ being $2$-chromatic (or having property B), see
[901].
This is true, and a proof was given in the comment section by Koishi Chan.
View the LaTeX source
This page was last edited 01 October 2025.
Additional thanks to: Stijn Cambie and Koishi Chan
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1027, https://www.erdosproblems.com/1027, accessed 2026-01-16
