We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters &#x03B2; (the interaction) and &#x03BB; (the external field), except for the case |&#x03BB;|=1 (the zero-field case). A randomized algorithm (FPRAS) for all graphs, and all &#x03B2;,&#x03BB; has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the decay of correlations property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions. Our approach extends to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters. In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.
The problem of computing partition functions has been widely studied, not only in statistical physics but also in combinatorics, because the partition function is often a generating function for combinatorial objects (cuts, in the case of the Ising model). There has been much progress on , which attempt to completely classify these problems as being either #P-hard or computable (exactly) in polynomial time (see, e.g., @cite_7 @cite_4 ).
@cite_4 @cite_7
2092436554 2005716876
Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of @math -colorings or the number of independent sets of a graph and also the partition functions of certain “spin glass” models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill [Random Structures Algorithms, 17 (2000), pp. 260-289] and Bulatov and Grohe [Theoret. Comput. Sci., 348 (2005), pp. 148-186], we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or #P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or #P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by Hadamard matrices (these turn out to be central in our proofs) we obtain a simple algebraic tractability criterion, which says that the tractable cases are those “representable” by a quadratic polynomial over the field @math . Graph homomorphism problem has been studied intensively. Given an m × m symmetric matrix A, the graph homomorphism function ZA(G) is defined as ZA(G) = σξ:V →[m] (u,v)∈E ΠAξ(u),ξ(v), where G = (V,E) is any undirected graph. The function ZA(G) can encode many interesting graph properties, including counting vertex covers and k-colorings. We study the computational complexity of ZA(G), for arbitrary complex valued symmetric matrices A. Building on the work by Dyer and Greenhill [1], Bulatov and Grohe [2], and especially the recent beautiful work by Goldberg, Grohe, Jerrum and Thurley [3], we prove a complete dichotomy theorem for this problem.