CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Entropy compression and the Lovasz Local Lemma
Org: Michael Molloy (University of Toronto)

Stochastic Local Search and the Lovasz Local Lemma  [PDF]

We present techniques for analyzing focused stochastic local search algorithms in discrete spaces. These are algorithms which search a state space probabilistically by repeatedly selecting a constraint that is violated in the current state and moving to a random nearby state which, hopefully, addresses the violation without introducing many new ones. The techniques we consider arise from recent works on the algorithmic aspects of the Lovasz Local Lemma, a non-constructive tool for proving the existence of satisfying states.

GWENAEL JORET, Université Libre de Bruxelles
Improved bound for AVD edge coloring  [PDF]

A proper edge coloring of a graph is 'adjacent vertex distinguishing' (AVD) if no two adjacent vertices see the same set of colors. Using a clever application of the Local Lemma, Hatami (2006) proved that every graph with maximum degree D and no isolated edge has an AVD edge coloring with D + 300 colors, provided D is large enough. In this talk, I will outline a proof that D + 19 colors are enough, using entropy compression techniques. This is motivated by the conjecture that D + 2 colors are in fact enough. Joint work with William Lochet.

PIOTR MICEK, Jagiellonian University
Nonrepetitive colorings and entropy compression method  [PDF]

A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that 3 symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of 3-element sets $L_1,\ldots,L_n$ there exists a nonrepetitive sequence $s_1,\ldots,s_n$ with $s_i$ in $L_i$. We present an elementary proof that sets of size 4 suffice. The argument is perhaps the most instructive application of the so-called entropy compression method. Joint work with Jarosław Grytczuk and Jakub Kozik.

MICHAEL MOLLOY, University of Toronto
Colouring graphs with small clique number  [PDF]

We prove that every triangle-free graph with maximum degree $\Delta$ has list chromatic number at most $(1+o(1))\frac{\Delta}{\ln \Delta}$. This improves the constant in a classic result of Johannson and matches the best-known bound for graphs of girth at least five. We also provide a new proof of Johannson’s result that for any $r\geq4$ every $K_r$-free graph has list-chromatic number at most $200r\frac{\Delta\ln\ln\Delta}{\ln\Delta}$. Both proofs are significantly simpler than Johannson’s original arguments.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology