On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász Local Lemma

Schweitzer [Inform. Process. Lett. 109 (2009) 229–232] described a connection between the incompressibility method and the Lovász Local Lemma. The idea was illustrated on the problem of lower bounding van der Waerden numbers. However, his result using incompressibility is worse than that obtained by Local Lemma by a multiplicative factor of 4/e4/e. In this paper we improve his method to give exactly the same result as the Lovász Local Lemma.

Research highlights► Incompressibility arguments sometimes give us identical results as Local Lemma. ► We present case study for lower bounding of Van der Waerden numbers. ► We sharpen similar result of Pascal Schweitzer.