| Monday, October 22nd, 2012 | 4:00pm-5:00pm | Burnside 1205 |
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.