Skip to Main content Skip to Navigation
Book sections

An Alternate Proof of the Algorithmic Lovász Local Lemma

Abstract : The algorithm for Lovász Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects satisfying a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm. We apply our technique to improve the best known upper bound to acyclic chromatic index.
Document type :
Book sections
Complete list of metadatas
Contributor : Isabelle Gouat <>
Submitted on : Thursday, January 25, 2018 - 12:26:14 PM
Last modification on : Monday, May 4, 2020 - 9:42:03 AM




Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos. An Alternate Proof of the Algorithmic Lovász Local Lemma. Extended Abstracts Summer 2015, 6, pp.61-65, 2017, Trends in Mathematics, 978-3-319-51752-0. ⟨10.1007/978-3-319-51753-7_10⟩. ⟨lirmm-01692634⟩



Record views