Improved algorithms for colorings of simple hypergraphs and applications

The famous Lovász Local Lemma was derived in the paper of P. Erdős and Lovász to prove that any $n$-uniform non-$r$-colorable hypergraph $H$ has maximum edge degree at least
$$ \Delta(H) \geq \frac14 r^{n-1}. $$
A long series of papers is devoted to the improvement of this classical result for different classesof uniform hypergraphs.
In our work we deal with colorings of simple hypergraphs, i.e. hypergraphs in which everytwo distinct edges do not share more than one vertex. By using a multipass random recoloringwe show that any simple $n$-uniform non-$r$-colorable hypergraph $H$ has maximum edge degree at least
$$ \Delta(H) \geq c \cdot nr^{n-1}, $$
where $c > 0$ is an absolute constant. We also give some applications of our probabilistic technique, we establish a new lower bound for the Van der Waerden number and extend the main result to the $b$-simple case.