Logo
All Random Solved Random Open
OPEN
Let $m(n)$ be minimal such that there is an $n$-uniform hypergraph with $m(n)$ edges which is $3$-chromatic. Estimate $m(n)$.
In other words, the hypergraph does not have Property B. Property B means that there is a set $S$ which intersects all edges and yet does not contain any edge.

It is known that $m(2)=3$, $m(3)=7$, and $m(4)=23$. Erdős proved \[2^n \ll m(n) \ll n^2 2^n\] (the lower bound in [Er63b] and the upper bound in [Er64e]). Erdős conjectured that $m(n)/2^n\to \infty$, which was proved by Beck [Be77], who proved $m(n)\gg (\log n)2^n$, and later [Be78] improved this to \[n^{1/3-o(1)}2^n \ll m(n).\] Radhakrishnan and Srinivasan [RaSr00] improved this to \[\sqrt{\frac{n}{\log n}}2^n \ll m(n).\] Pluhar [Pl09] gave a very short proof that $m(n) \gg n^{1/4}2^n$.

Additional thanks to: Jozsef Balogh