Monday, October 22nd, 2012 | 4:00pm-5:00pm | Burnside 1205 |

Department of Mathematics and Statistics, McGill University

Nonrepetitive Coloring via Entropy Compression

A vertex coloring of a graph is nonrepetitive if there is no path
whose first half receives the same sequence of colors as the second
half. As for many other graph coloring problems, Lovasz's Local Lemma
can be used to obtain nonrepetitive colorings where the number of
colors is bounded by a function of the maximum degree Δ. This was
first observed by Alon et al in 2002, who obtained a bound of
c\Δ^{2} for some large constant c. The value of the constant c was
subsequently improved several times over the years, down to c = 12.92
by Haranta and Jendrol in 2012.

In this talk I will present a proof for c = 1. The proof is based on the entropy compression method introduced by Moser and Tardos in their constructive proof of the Local Lemma. A general message of the talk will be that their approach is not only very useful to obtain efficient algorithms, but can moreover be used to get improved bounds, often with simpler proofs.

Joint work with Vida Dujmovic, Jakub Kozik, and David Wood.