Computing the partition function for graph homomorphisms
From MaRDI portal
Publication:681595
DOI10.1007/s00493-016-3357-2zbMath1399.05209arXiv1406.1771OpenAlexW2963793606MaRDI QIDQ681595
Pablo Soberón, Alexander I. Barvinok
Publication date: 12 February 2018
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.1771
Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs, Computing the permanent of (some) complex matrices, Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing, Absence of zeros implies strong spatial mixing, A dichotomy for bounded degree graph homomorphisms with nonnegative weights, A short proof of the equivalence of left and right convergence for sparse graphs, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, The Ising partition function: zeros and deterministic approximation, On a conjecture of Sokal concerning roots of the independence polynomial, Fisher zeros and correlation decay in the Ising model, Fisher Zeros and Correlation Decay in the Ising Model
Cites Work
- Unnamed Item
- Unnamed Item
- Computing the permanent of (some) complex matrices
- Homomorphisms of edge-colored graphs and Coxeter groups
- Zero knowledge and the chromatic number
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The complexity of partition functions
- Counting independent sets up to the tree threshold
- Computing the partition function for cliques in a graph
- Approximate graph coloring by semidefinite programming
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Coloring -colorable graphs using relatively small palettes
- Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
- Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem
