Algorithms, Combinatorics and Optimization Seminar Mike Molloy
University of Toronto
Title: Entropy Compression and the Lovasz Local Lemma

Abstract: The Lovasz Local Lemma, a cornerstone of the probabilistic method, is a powerful and widely used proof technique. In 2009, Moser introduced a technique called entropy compression to provide efficient algorithms which construct objects that the Local Lemma guarantees to exist. Recently, entropy compression has been used to develop more powerful versions of the Local Lemma which provide existence proofs in settings where the original Local Lemma does not apply.

I will illustrate this technique with applications to graph colouring: (a) colouring triangle-free graphs, and (b) frugal colouring, where no colour can appear too many times in any neighbourhood.

Date: Thursday, January 19, 2017
Time: 3:30 pm
Location: Wean Hall 8220
Note: before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220.