Correlation decay and the absence of zeros property of partition functions
From MaRDI portal
(Redirected from Publication:6077053)
Abstract: Absence of (complex) zeros property is at the heart of the interpolation method developed by Barvinok cite{barvinok2017combinatorics} for designing deterministic approximation algorithms for various graph counting and computing partition functions problems. Earlier methods for solving the same problem include the one based on the correlation decay property. Remarkably, the classes of graphs for which the two methods apply sometimes coincide or nearly coincide. In this paper we show that this is more than just a coincidence. We establish that if the interpolation method is valid for a family of graphs satisfying the self-reducibility property, then this family exhibits a form of correlation decay property which is asymptotic Strong Spatial Mixing (SSM) at distances , where is the number of nodes of the graph. This applies in particular to amenable graphs, such as graphs which are finite subsets of lattices. Our proof is based on a certain graph polynomial representation of the associated partition function. This representation is at the heart of the design of the polynomial time algorithms underlying the interpolation method itself. We conjecture that our result holds for all, and not just amenable graphs.
Recommendations
- Fisher zeros and correlation decay in the Ising model
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Approximate counting via correlation decay in spin systems
- Correlation decay and deterministic FPTAS for counting colorings of a graph
Cites work
- Algorithmic Pirogov-Sinai theory
- Algorithms for \#BIS-hard problems on expander graphs
- Approximating real-rooted and stable polynomials, with combinatorial applications
- Benjamini-Schramm continuity of root moments of graph polynomials
- Combinatorics and complexity of partition functions
- Completely analytical interactions: Constructive description
- Computing the independence polynomial: from the tree threshold down to the roots
- Computing the partition function for cliques in a graph
- Computing the partition function of a polynomial on the Boolean cube
- Computing the permanent of (some) complex matrices
- Correlation decay and deterministic FPTAS for counting colorings of a graph
- Correlation decay up to uniqueness in spin systems
- Countable state space Markov random fields and Markov chains on trees
- Counting independent sets up to the tree threshold
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Gibbs measures and phase transitions
- scientific article; zbMATH DE number 3951995 (Why is no real title available?)
- scientific article; zbMATH DE number 1023434 (Why is no real title available?)
- scientific article; zbMATH DE number 2148179 (Why is no real title available?)
- scientific article; zbMATH DE number 1885142 (Why is no real title available?)
- Improved FPTAS for multi-spin systems
- Markov random fields on an infinite tree
- On a conjecture of Sokal concerning roots of the independence polynomial
- Phase coexistence and slow mixing for the hard-core model on \(\mathbb Z^{2}\)
- Phase coexistence and torpid mixing in the 3-coloring model on \({\mathbb Z}^d\)
- Strong spatial mixing of list coloring of graphs
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Uniqueness of uniform random colorings of regular trees
Cited in
(8)- Poincaré-Lelong approach to universality and scaling of correlations between zeros
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Zero energy states and decay of correlations
- Fisher zeros and correlation decay in the Ising model
- Absence of zeros implies strong spatial mixing
- Smoothed counting of 0–1 points in polyhedra
- Deterministic approximate counting of colorings with fewer than 2 colors via absence of zeros
- On the zeros of partition functions with multi-spin interactions
This page was built for publication: Correlation decay and the absence of zeros property of partition functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6077053)
