Achlioptas, Dimitris ;
Zampetakis, Kostas
Local Approximations of the Independent Set Polynomial
Abstract
The independent set polynomial of a graph has one variable for each vertex and one monomial for each independent set, comprising the product of the corresponding variables. Given a graph G on n vertices and a vector p ∈ [0,1)ⁿ, a central problem in statistical mechanics is determining whether the independent set polynomial of G is nonvanishing in the polydisk of p, i.e., whether Z_G(x) > 0 for every x ∈ ℂⁿ such that x_i ≤ p_i. Remarkably, when this holds, Z_G(p) is a lower bound for the avoidance probability when G is a dependency graph for n events whose probabilities form vector p. A local sufficient condition for Z_G > 0 in the polydisk of p is the Lovász Local Lemma (LLL).
In this work we derive several new results on the efficient evaluation and bounding of Z_G. Our starting point is a monotone mapping from subgraphs of G to truncations of the tree of selfavoiding walks of G. Using this mapping our first result is a local upper bound for Z(p), similar in spirit to the local lower bound for Z(p) provided by the LLL. Next, using this mapping, we show that when G is chordal, Z_G can be computed exactly and in linear time on the entire complex plane, implying perfect sampling for the hardcore model on chordal graphs. We also revisit the task of bounding Z(p) from below, i.e., the LLL setting, and derive four new lower bounds of increasing sophistication. Already our simplest (and weakest) bound yields a strict improvement of the famous asymmetric LLL, i.e., a strict relaxation of the inequalities of the asymmetric LLL without any further assumptions. This new asymmetric local lemma is sharp enough to recover Shearer’s optimal bound in terms of the maximum degree Δ(G). We also apply our more sophisticated bounds to estimate the zerofree region of the hardcore model on the triangular lattice (hard hexagons model).
BibTeX  Entry
@InProceedings{achlioptas_et_al:LIPIcs.ICALP.2021.8,
author = {Achlioptas, Dimitris and Zampetakis, Kostas},
title = {{Local Approximations of the Independent Set Polynomial}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {8:18:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14077},
URN = {urn:nbn:de:0030drops140773},
doi = {10.4230/LIPIcs.ICALP.2021.8},
annote = {Keywords: Independent Set Polynomial, Lov\'{a}sz Local Lemma, Selfavoiding Walks}
}
02.07.2021
Keywords: 

Independent Set Polynomial, Lovász Local Lemma, Selfavoiding Walks 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 