Volume 13 (2017) Article 17 pp. 1-41
A Constructive Lovász Local Lemma for Permutations
Revised: December 30, 2016
Published: December 21, 2017
[PDF (364K)]    [PS (4100K)]    [PS.GZ (752K)]
[Source ZIP]
Keywords: Lovász Local Lemma, Lopsided Lovász Local Lemma, random permutations, Moser-Tardos algorithm, Latin transversals, rainbow Hamiltonian cycles, strong chromatic number, hypergraph packing
ACM Classification: F.2.2, G.3
AMS Classification: 68W20, 60C05, 05B15

Abstract: [Plain Text Version]

$\newcommand{\cclass}[1]{{\textsf{#1}}}$

While there has been significant progress on algorithmic aspects of the Lovász Local Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context of random permutations. The breakthrough algorithm of Moser & Tardos only works in the setting of independent variables, and does not apply in this context. We resolve this by developing a randomized polynomial-time algorithm for such applications. A noteworthy application is for Latin transversals: the best general result known here (Bissacot et al., improving on Erdős and Spencer), states that any $n \times n$ matrix in which each entry appears at most $(27/256)n$ times, has a Latin transversal. We present the first polynomial-time algorithm to construct such a transversal. We also develop $\cclass{RNC}$ algorithms for Latin transversals, rainbow Hamiltonian cycles, strong chromatic number, and hypergraph packing.

In addition to efficiently finding a configuration which avoids bad events, the algorithm of Moser & Tardos has many powerful extensions and properties. These include a well-characterized distribution on the output distribution, parallel algorithms, and a partial resampling variant. We show that our algorithm has nearly all of the same useful properties as the Moser--Tardos algorithm, and present a comparison of this aspect with recent work on the LLL in general probability spaces.

An extended abstract of this paper has appeared in the Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms, 2014.