Complexity of Ising polynomials

DOI10.1017/S0963548312000259zbMATH Open1247.82011arXiv1110.3639MaRDI QIDQ2911072FDOQ2911072

Authors: Tomer Kotek 

Publication date: 12 September 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: This paper deals with the partition function of the Ising model from statistical mechanics, which is used to study phase transitions in physical systems. A special case of interest is that of the Ising model with constant energies and external field. One may consider such an Ising system as a simple graph together with vertex and edge weights. When these weights are considered indeterminates, the partition function for the constant case is a trivariate polynomial Z(G;x,y,z). This polynomial was studied with respect to its approximability by L. A. Goldberg, M. Jerrum and M. Paterson in 2003. Z(G;x,y,z) generalizes a bivariate polynomial Z(G;t,y), which was studied by D. Andr'{e}n and K. Markstr"{o}m in 2009. We consider the complexity of Z(G;t,y) and Z(G;x,y,z) in comparison to that of the Tutte polynomial, which is well-known to be closely related to the Potts model in the absence of an external field. We show that Z(G;x,y,z) is #P-hard to evaluate at all points in $mathbb{Q}^3$, except those in an exception set of low dimension, even when restricted to simple graphs which are bipartite and planar. A counting version of the Exponential Time Hypothesis, #ETH, was introduced by H. Dell, T. Husfeldt and M. Wahl'{e}n in 2010 in order to study the complexity of the Tutte polynomial. In analogy to their results, we give a dichotomy theorem stating that evaluations of Z(G;t,y) either take exponential time in the number of vertices of $G$ to compute, or can be done in polynomial time. Finally, we give an algorithm for computing Z(G;x,y,z) in polynomial time on graphs of bounded clique-width, which is not known in the case of the Tutte polynomial.

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

Recommendations

• The Complexity of Ferromagnetic Ising with Local Fields
• The complexity of approximating complex-valued Ising and Tutte partition functions
• The bivariate Ising polynomial of a graph
• The complexity of partition functions
• The computational complexity of knot and matroid polynomials

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph polynomials (05C31) Planar graphs; geometric and topological aspects of graph theory (05C10) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cites Work

• The bivariate Ising polynomial of a graph
• Title not available (Why is that?)
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• The complexity of partition functions
• On the computational complexity of the Jones and Tutte polynomials
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The Computational Complexity of Tutte Invariants for Planar Graphs
• Polynomial-Time Approximation Algorithms for the Ising Model
• The computational complexity of two‐state spin systems
• Computational complexity of counting problems on 3-regular planar graphs
• Title not available (Why is that?)
• Algorithmic uses of the Feferman-Vaught theorem
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Approximating partition functions of the two-state spin system
• Computing the Tutte Polynomial on Graphs of Bounded Clique‐Width

Cited In (6)

• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• Optimal sufficient requirements on the embedded Ising problem in polynomial time
• The complexity of approximating complex-valued Ising and Tutte partition functions
• Bipartition polynomials, the Ising model, and domination in graphs
• New graph polynomials from the Bethe approximation of the Ising partition function
• The bivariate Ising polynomial of a graph

This page was built for publication: Complexity of Ising polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2911072)