Speaker: Gorjan Alagic
 
Day:  Wednesday, 12/1/2004
Room: ITE 336
Time:  3:30pm-4:10pm 

Title: The Local Lemma
----------------------------------------------------------------------------

The probabilistic method is a powerful proof tool in discrete
mathematics. Instead of trying to prove the existence of an object
constructively, or by other traditional methods, we define a
probability space over a large number of objects that are in some way
similar to the one we are looking for. The task is then to show that
the probability of finding our object is nonzero. This is quite
simple for cases where there is no mutual independence. For example,
it is trivial to see that a series of n all-heads coin tosses exists.
We know that among all series of n independent tosses, it occurs with
probability 2^(-n) > 0.
     The question then arises: can we conclude the same if there is some
small amount of dependence between our events? The Local Lemma, first
proved in 1975 by Erdos and Lovasz, gives a beautiful and simple
condition for when we can do just that. In this talk, we will state
and prove the lemma, and give a nice graph-theoretic application.

back to CSE-TS page