CanaDAM 2017 UniversitÃ© Ryerson, 12 - 16 juin 2017 canadam.math.ca/2017f
 english accueil réunion accueil canadam

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

FOTIS ILIOPOULOS, UC Berkeley
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.