A new randomized algorithm for the Erdos--Hajnal problem

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.

No reviews yet.

No comments yet.