DIMACS - Graduate Student Combinatorics Seminar

Title: The Local Lemma and its Applications

Speaker: Wesley Pegden, Rutgers University

Date: Wednesday, October 21, 2009 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


The Lovasz Local Lemma is a power tool in probabilistic combinatorics. In contrast to simpler probabilistic proof techniques, the Local Lemma allows probabilistic proofs for the existence of even very rare combinatorial objects. In this talk, I will state and "interpret" the Local Lemma, and show how it can be applied in a variety of situations. I will also discuss some common pitfalls (we will "prove" that a triangle can be 2-colored).

Time permitting, I will talk some about my research on applications of the Local Lemma to games.