Zero-free regions of partition functions with applications to algorithms and graph limits
From MaRDI portal
Publication:1786055
DOI10.1007/s00493-016-3506-7zbMath1424.05236arXiv1507.02089OpenAlexW2962684356MaRDI QIDQ1786055
Publication date: 24 September 2018
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.02089
Graph polynomials (05C31) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)
Related Items (6)
On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs ⋮ Zeros and approximations of holant polynomials on the complex plane ⋮ Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ Computing the Partition Function of a Polynomial on the Boolean Cube ⋮ Approximating permanents and hafnians ⋮ On a conjecture of Sokal concerning roots of the independence polynomial
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
- Tensor invariants for certain subgroups of the orthogonal group
- Characterizing partition functions of the vertex model
- Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin.
- Approximating the partition function of planar two-state spin systems
- Graph invariants related to statistical mechanical models: Examples and problems
- Computing the partition function for graph homomorphisms with multiplicities
- Benjamini-Schramm continuity of root moments of graph polynomials
- 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
- Complex zero-free regions at large \(|q|\) for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Improved FPTAS for Multi-spin Systems
- Counting independent sets up to the tree threshold
- From Holant to #CSP and Back: Dichotomy for Holant c Problems
- Computational Complexity of Holant Problems
- Computing the partition function for cliques in a graph
- Approximating the Partition Function of the Ferromagnetic Potts Model
- Edge coloring models and reflection positivity
- Simulating Quantum Computation by Contracting Tensor Networks
- On Approximately Counting Colorings of Small Degree Graphs
- Left and right convergence of graphs with bounded degree
- Holant problems and counting CSP
- Quantum Computation and the Evaluation of Tensor Networks
- Automata, Languages and Programming
- A complete dichotomy rises from the capture of vanishing signatures
- Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem
This page was built for publication: Zero-free regions of partition functions with applications to algorithms and graph limits
