Finding Lovasz's Needle in an Exponential Haystack

Finding Lovasz's Needle in an Exponential Haystack

-
Joel Spencer, Courant Institute for Mathematics, NYC
Fine Hall 224

The Lovasz Local Lemma is a subtle and far-reaching probability lemma. Roughly, given a large number of bad events which are "mostly" independent it sieves out an instance when none of the bad events occur. As an illustrative example, consider a huge family of 10-element sets, where each set overlaps at most 100 others. We color randomly red and blue and for each set e there is a bad event that e is monochromatic. The conclusion is the existence of a coloring where none of the e are monochromatic. In theory. But if there are n sets a random coloring only has exponentially small chance of succeeding. Finding a polynomial time algorithmic implementation has proven elusive. There were some results of Jozsef Beck and Noga Alon in the early 1990s but they had limited application. Very recently Robin Moser (ETH) has made a breakthrough, giving an amazingly simple probabilistic algorithm to find the coloring and a not quite so simple proof that the algorithm indeed works.We shall rephrase Moser's argument and give the entire argument.