School of Technology and Computer Science Seminars
Constructive and Non-constructive Aspects of the Lovasz Local Lemma
by Prof. Aravind Srinivasan (University of Maryland, USA)
Tuesday, July 2, 2013
from
to
(Asia/Kolkata)
at Colaba Campus ( AG-69 )
at Colaba Campus ( AG-69 )
Description |
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? |