Rutgers Discrete Mathematics Seminar

Title: Connecting three Local Lemmas

Speaker: Wes Pegden, NYU

Date: Tuesday, February 1, 2011 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


Three recent results on the Local Lemma include a Lefthanded version which allows a 'one-sided' view of dependencies, a result of Bissacot, et al. improving the Lov'asz Local Lemma by giving a better approximation to an old characterization of Shearer by using techniques from the cluster expansion in statistical mechanics, and the recent breakthrough of Moser and Tardos, which gives an algorithmic version of the Local Lemma which is nearly as general as the standard Lov'asz Local Lemma. In this talk, we will discuss three new theorems connecting these independent versions of the Local Lemma.