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.