University of Athens and CTI & Press



On the algorithmic Lovász Local Lemma and acyclic edge coloring


The algorithm by Moser and Tardos for the Lovász Local Lemma gives a constructive way to prove the existence of combinatorial objects that satisfy a system of constraints. In this talk, I will first present an alternative probabilistic analysis of the algorithm that does not involve counting witness-trees, neither reconstructing the history of the algorithm from the witness tree. I will then use this approach to show, in a fairly simple way, that a graph with maximum degree Δ has an acyclic proper edge coloring with at most 3.732(Δ – 1) + 1 colors, improving the previous known bound of 4(Δ – 1). Time permitting, I will discuss about applications to other problems as well.

This is joint work with Ioannis Giotis, Kostas Psaromiligkos and Dimitrios Thilikos.


The Catalan Mathematical Society invites participants to this first congress of a biannual series focusing on current research topics across several areas of Mathematics.

Plenary talks and thematic sessions have been selected by the Scientific Committee of the SCM. Special thanks are due to the organisers of the thematic sessions and to the local mathematical community as a whole for their support to this congress.


Societat Catalana de Matemàtiques
Institut d'Estudis Catalans
Carrer del Carme, 47
08001 Barcelona

Phone: +34 933 248 583

Download a poster (high res)

Download a poster (low res)