University of Athens and CTI & Press
Title
On the algorithmic Lovász Local Lemma and acyclic edge coloring
Abstract
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.
