Campus Event Calendar

Event Entry

What and Who

The Incompressibility Method and Lovász' Local Lemma

Pascal Schweitzer
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS  
AG Audience

Date, Time and Location

Wednesday, 14 May 2008
30 Minutes
E1 4


The incompressibility method and the probabilistic method both portray ideas that can be applied to obtain bounds for combinatorial problems.

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.


Pascal Schweitzer
--email hidden
passcode not visible
logged in users only

Pascal Schweitzer, 05/06/2008 13:40 -- Created document.