  In 1961 Erd\H{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 \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.
