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$.

In [ErLo75] Erdős and Lovász speculate that $n2^n$ is the correct order of magnitude for $m(n)$.

View the LaTeX source

This page was last edited 28 December 2025.