A new randomized algorithm for the Erdos--Hajnal problem

Original · EN

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₁ √n/ n 2ⁿ and c₂ n² 2ⁿ respectively. The lower bound is due to Radhakrishnan and Srinivasan (see 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) ≥ c nʳ⁻¹/ʳ rⁿ⁻¹, 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 RS of Radhakrishnan and Srinivasan, and our proof is simpler.