Tata Institute of Fundamental Research
Constructive and Non-constructive Aspects of the Lovasz Local Lemma
Seminar
Speaker:
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)
Organiser:
Jaikumar Radhakrishnan
Date:
Monday, 1 Jul 2013, 14:30 to 17:00
Venue:
A-269 (DAA Seminar)
(Scan to add to calendar)
Abstract:
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?
| Speaker: | 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) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Monday, 1 Jul 2013, 14:30 to 17:00 |
| Venue: | A-269 (DAA Seminar) |
(Scan to add to calendar)
Abstract:
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?