A new randomized algorithm for the Erdos--Hajnal problem

Abstract: In 1961 ErdH{o}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} s q r t f r a c n l n 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) g e c n^{f r a c 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.

This page was built for publication: A new randomized algorithm for the Erdos--Hajnal problem