A new randomized algorithm for the Erdos--Hajnal problem

Abstract

In 1961 Erdős and Hajnal introduced the quantity $m(n)$ as the minimum number of edges in an $n$-uniform hypergraph with chromatic number at least 3. The best known lower and upper bounds for $m(n)$ are $c_1\sqrt{\frac{n}{\ln n}}{2}^n$ and $c_2{n}^2{2}^n$ respectively. The lower bound is due to Radhakrishnan and Srinivasan (see \cite{RS}). A natural generalization for $m(n)$ is the quantity $m(n,r)$, which is the minimum number of edges in an $n$-uniform hypergraph with chromatic number at least $r+1$. In this work, we present a new randomized algorithm yielding a bound $m(n,r)\ge c{n}^{\frac{r-1}{r}}{r}^{n-1}$, which improves upon all the previous bounds in a wide range of the parameters $n,r$. Moreover, for $r=2$, we get exactly the same bound as in the work \cite{RS} of Radhakrishnan and Srinivasan, and our proof is simpler.