TY - JOUR

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

AU - Giotis, Ioannis

AU - Kirousis, Lefteris

AU - Livieratos, John

AU - Psaromiligkos, Kostas I.

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© 2018 Copyright by the paper's authors.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85049079008&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049079008&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85049079008

SN - 1613-0073

VL - 2113

SP - 148

EP - 155

JO - CEUR Workshop Proceedings

JF - CEUR Workshop Proceedings

T2 - 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures, GASCom 2018

Y2 - 18 June 2018 through 20 June 2018

ER -