Student Probability Seminar

The Lovasz Local Lemma and a Couple of Its Magical Applications

Speaker: Moumanti Podder

Location: Warren Weaver Hall 1314

Date: Thursday, October 15, 2015, 2 p.m.

Synopsis:

The Lovasz Local Lemma, which is an extremely powerful tool in probabilistic combinatorics, is really a generalization of the case of mutual independence of events to the scenario where there is rare dependencies among them. It helps to show that in certain cases, none of the finitely many "bad events" occur with positive probability. And it has some stunning uses, for example, providing sufficient conditions for the 2-colourability of hypergraphs, and exploring the properties of colourings of the real line. I hope to be able to give a concise proof of the lemma, and discuss two such nice applications.