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.
arXiv commentBased on comments of the referees some changes have been made to make. 21 pages. To appear in Combinatorica
References in corpus (9)
- Simulating quantum computation by contracting tensor networks
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Approximating the partition function of the ferromagnetic Potts model
- The computational hardness of counting in two-spin models on d-regular graphs
- Complex zero-free regions at large |q| for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
- A Complete Dichotomy Rises from the Capture of Vanishing Signatures
- Approximating permanents and hafnians
- Benjamini--Schramm continuity of root moments of graph polynomials
- Approximating the partition function of planar two-state spin systems