A counting argument for graph colouring
Time: 11:00 -- Location: LRI, 445
summary: In 2010, Moser and Tardos introduced an algorithmic version of the celebrated Lovász Local Lemma using the entropy compression method. Their method is now widely used in the community and has become a standard of the probabilistic method, mainly because it often provides the tightest existential bounds. However, it suffers from a major drawback ; the proofs requiring entropy compression are often very technical, which makes them hard to understand for the reader. In this talk, I will present a simple counting argument that can systematically replace entropy compression in its most straightforward uses. The main goal of this talk will be to provide a short proof of the Johansson-Molloy theorem stating that every triangle-free graph of maximum degree Δ has chromatic number at most (1+o(1)) Δ/ln Δ, using that counting argument instead of entropy compression. Joint work with Eoin Hurley.