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

DOI10.1002/rsa.20236zbMath1157.82006MaRDI 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

05C30: Enumeration in graph theory

82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

Related Items

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

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