Constructive and Non-constructive Aspects of the Lovasz Local Lemma


Aravind Srinivasan


University of Maryland at College Park
Department of Computer Science
Room 3263, A.V. Williams Building
College Park, MD 20742
United States of America


Monday, 1 July 2013, 14:30 to 17:00


  • A-269 (DAA Seminar)


In three talks, I will describe aspects of the Local Lemma that have recently been uncovered by Moser & Tardos, Pegden, and David Harris and myself. As a running example, we will consider the following type of "graph transversal" problem introduced by Bollobas, Erdos and Szemeredi in the 1970s: given a graph $G = (V,E)$ and an integer $s$, for how small a $b$ can we guarantee that no matter how $V$ has been partitioned into blocks, each of size at least $b$, there is a way of choosing one vertex from each block such that the chosen vertices do not induce a clique on $s$ vertices?