Improving Gebauer's construction of 3-chromatic hypergraphs with few edges

Jakub Kozik

In 1964 Erdős proved, by randomized construction, that the minimum number of edges in a $k$-graph that is not two colorable is $O(k^2{2}^k)$. To this day, it is not known whether…