Correlation decay and the absence of zeros property of partition functions

DOI10.1002/rsa.21083zbMath1522.05467arXiv2011.04915OpenAlexW3103794091MaRDI QIDQ6077053

David Gamarnik

Publication date: 17 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.04915

zbMATH Keywords

partition functiongraph algorithmcountingstatistical physicscliquesubgraph density

Mathematics Subject Classification ID

Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Absence of zeros implies strong spatial mixing ⋮ Smoothed counting of 0–1 points in polyhedra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the permanent of (some) complex matrices
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Combinatorics and complexity of partition functions
• Countable state space Markov random fields and Markov chains on trees
• Benjamini-Schramm continuity of root moments of graph polynomials
• Gibbs measures and phase transitions
• Markov random fields on an infinite tree
• Uniqueness of uniform random colorings of regular trees
• Completely analytical interactions: Constructive description
• Algorithmic Pirogov-Sinai theory
• On a conjecture of Sokal concerning roots of the independence polynomial
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Phase Coexistence and Slow Mixing for the Hard-Core Model on ℤ2
• Improved FPTAS for Multi-spin Systems
• Counting independent sets up to the tree threshold
• Algorithms for #BIS-Hard Problems on Expander Graphs
• Computing the partition function for cliques in a graph
• 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
• Computing the Partition Function of a Polynomial on the Boolean Cube
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Approximating real-rooted and stable polynomials, with combinatorial applications
• Strong spatial mixing of list coloring of graphs
• Phase coexistence and torpid mixing in the 3-coloring model on ${\mathbb Z}^d$
• Correlation Decay up to Uniqueness in Spin Systems

This page was built for publication: Correlation decay and the absence of zeros property of partition functions