Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models

DOI10.1002/rsa.20236zbMath1157.82006OpenAlexW4235998730MaRDI QIDQ3608304

Antar Bandyopadhyay, David Gamarnik

Publication date: 4 March 2009

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

Full work available at URL: https://doi.org/10.1002/rsa.20236

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Related Items (max. 100)

Spatial mixing and the connective constant: optimal bounds ⋮ Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs ⋮ Evaluations of Tutte polynomials of regular graphs ⋮ Extremal Regular Graphs: Independent Sets and Graph Homomorphisms ⋮ Total variation discrepancy of deterministic random walks for ergodic Markov chains ⋮ Computing the partition function for graph homomorphisms with multiplicities ⋮ The mean field traveling salesman and related problems ⋮ Harnessing the Bethe free energy ⋮ Correlation decay and the absence of zeros property of partition functions ⋮ Correlation decay and deterministic FPTAS for counting colorings of a graph ⋮ Near-Optimal Distributed Linear-Quadratic Regulator for Networked Systems ⋮ Approximating partition functions of the two-state spin system ⋮ Online Edge Coloring via Tree Recurrences and Correlation Decay ⋮ Computing the Partition Function of a Polynomial on the Boolean Cube ⋮ Replica symmetry of the minimum matching ⋮ Factor models on locally tree-like graphs ⋮ Random cluster model on regular graphs ⋮ A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix ⋮ Dismantlability, connectedness, and mixing in relational structures ⋮ Left and right convergence of graphs with bounded degree ⋮ Charting the replica symmetric phase ⋮ Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees ⋮ Endogeny for the logistic recursive distributional equation ⋮ Strong spatial mixing in homomorphism spaces ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ Fisher zeros and correlation decay in the Ising model ⋮ Approximating the partition function of planar two-state spin systems ⋮ Dismantlability, Connectedness, and Mixing in Relational Structures ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Uniqueness of Gibbs measures for continuous hardcore models ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes ⋮ Weighted enumeration of spanning subgraphs in locally tree-like graphs ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Strong spatial mixing of list coloring of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of max-type recursive distributional equations
• Countable state space Markov random fields and Markov chains on trees
• The complexity of computing the permanent
• Gibbs measures and phase transitions
• Markov random fields on an infinite tree
• Information flow on trees
• Uniqueness of uniform random colorings of regular trees
• Linear phase transition in random linear constraint satisfaction problems
• Counting and sampling \(H\)-colourings
• Randomly coloring constant degree graphs
• Counting independent sets up to the tree threshold
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Approximating the Permanent
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• Dynamics and endogeny for recursive processes on trees
• Invariant probability measures and dynamics of exponential linear type maps
• A random polynomial-time algorithm for approximating the volume of convex bodies
• A second threshold for the hard‐core model on a Bethe lattice
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Prescribing a System of Random Variables by Conditional Distributions
• Combinatorial criteria for uniqueness of Gibbs measures

This page was built for publication: Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models