Computing the partition function for graph homomorphisms with multiplicities

DOI10.1016/j.jcta.2015.08.001zbMath1325.05114arXiv1410.1842OpenAlexW2962992138MaRDI QIDQ889510

Pablo Soberón, Alexander I. Barvinok

Publication date: 6 November 2015

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

algorithmpartition functiongraph homomorphism

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

An FPTAS for the hardcore model on random regular bipartite graphs, Algorithmic Pirogov-Sinai theory, Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials, Unnamed Item, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Computing the Partition Function of a Polynomial on the Boolean Cube, The Ising partition function: zeros and deterministic approximation, Approximating permanents and hafnians, Computing the partition function for cliques in a graph, Zero-free regions of partition functions with applications to algorithms and graph limits, 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
• On testing Hamiltonicity of graphs
• A fast algorithm for equitable coloring
• Homomorphisms of edge-colored graphs and Coxeter groups
• Zero knowledge and the chromatic number
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• The complexity of partition functions
• Detecting high log-densities
• Computing the partition function for cliques in a graph
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Permanents
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem