The Incompressibility Method and Lovász' Local Lemma

Within the probabilistic method Lovász' Local Lemma has been used numerous times to show strong lower bounds, in many cases, especially for Ramsey type problems, yielding today's currently best known bounds.

In this talk I will first explain a classical concept of Ramsey Theory: the van der Waerden numbers. Taking them as an example I will recall how lower bounds for these integers can be obtained using the incompressibility method as well as the probabilistic method. I will show how the application of the incompressibility method to Ramsey problems can be strengthened to yield bounds in the same magnitude as those obtained via the Local Lemma.