Alternative proofs of the asymmetric Lovász local lemma and Shearer's lemma

Ioannis Giotis 1 Lefteris Kirousis 1 John Livieratos 1 Kostas Psaromiligkos 1 Dimitrios M. Thilikos 1, 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We provide new algorithmic proofs for two forms of the Lovász Local Lemma: the Asymmetric version and Shearer's Lemma. Our proofs directly compute an upper bound for the probability that the corresponding Moser-type algorithms last for at least n steps. These algorithms iteratively sample the probability space; when and if they halt, a correct sampling, i.e. one where all undesirable events are avoided, is obtained. Our computation shows that this probability is exponentially small in n. In contrast most extant proofs for the Lovász Local Lemma and its variants use counting arguments that give estimates of only the expectation that the algorithm lasts for at least n steps. For the asymmetric version, we use the results of Bender and Richmond on the multivariable Lagrange inversion. For Shearer's Lemma, we follow the work of Kolipaka and Szegedy, combined with Gelfand's formula for the spectral radius of a matrix.
Type de document :
Communication dans un congrès
GASCom: Random and Exhaustive Generation of Combinatorial Structures, Jun 2018, Athens, Greece. 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures, pp.148-155, 2018, 〈http://ceur-ws.org/Vol-2113/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01890510
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 8 octobre 2018 - 16:37:53
Dernière modification le : mardi 9 octobre 2018 - 01:14:47
Document(s) archivé(s) le : mercredi 9 janvier 2019 - 16:32:17

Fichier

paper15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01890510, version 1

Collections

Citation

Ioannis Giotis, Lefteris Kirousis, John Livieratos, Kostas Psaromiligkos, Dimitrios M. Thilikos. Alternative proofs of the asymmetric Lovász local lemma and Shearer's lemma. GASCom: Random and Exhaustive Generation of Combinatorial Structures, Jun 2018, Athens, Greece. 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures, pp.148-155, 2018, 〈http://ceur-ws.org/Vol-2113/〉. 〈lirmm-01890510〉

Partager

Métriques

Consultations de la notice

57

Téléchargements de fichiers

18