An alternative proof for the constructive Asymmetric Lovász Local Lemma

2015/05/11 by Ioannis Giotis, Giotis, Ioannis, Lefteris M. Kirousis +6
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #cs.DM #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1505.02568

arxiv created 2015/05/11 · openalex publication_date 2015/05/11 · arxiv updated 2015/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide an alternative constructive proof of the Asymmetric Lovász Local Lemma. Our proof uses the classic algorithmic framework of Moser and the analysis introduced by Giotis, Kirousis, Psaromiligkos, and Thilikos in "On the algorithmic Lovász Local Lemma and acyclic edge coloring", combined with the work of Bender and Richmond on the multivariable Lagrange Inversion formula.

Cited by

• On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring

Related

• A constructive proof of the general lovász local lemma
• On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring
• A constructive proof of the general Lovasz Local Lemma
• Simple Local Computation Algorithms for the General Lovasz Local Lemma
• New Constructive Aspects of the Lovasz Local Lemma