School Seminars and Colloquia

How to use the Lovasz Local Lemma

Discrete Structures and Algorithms (Seminar)

by David Wood


Institution: The University of Melbourne, Department of Mathematics and Statistics
Date: Tue 4th August 2009
Time: 2:15 PM
Location: Room 107, Richard Berry Building, The University of Melbourne

Abstract: The Lovász Local Lemma is a powerful probabilistic tool for proving the existence of combinatorial objects.
In this informal talk I will explain the various versions of the Lovász Local Lemma, and illustrate how to use them by proving a number of theorems about graph colouring. No background in probability or graph theory will be assumed.

For More Information: contact: David Wood. email: woodd@unimelb.edu.au