Zero-free regions of partition functions with applications to algorithms and graph limits
arXiv:1507.02089 · doi:10.1007/s00493-016-3506-7
Abstract
Based on a technique of Barvinok and Barvinok and Soberón we identify a class of edge-coloring models whose partition functions do not evaluate to zero on bounded degree graphs. Subsequently we give a quasi-polynomial time approximation scheme for computing these partition functions. As another application we show that the normalised partition functions of these models are continuous with respect the Benjamini-Schramm topology on bounded degree graphs. We moreover give quasi-polynomial time approximation schemes for evaluating a large class of graph polynomials, including the Tutte polynomial, on bounded degree graphs.
Based on comments of the referees some changes have been made to make. 21 pages. To appear in Combinatorica