THE ISING PARTITION FUNCTION:
ZEROS AND DETERMINISTIC APPROXIMATION

arXiv:1704.06493v1 [] 21 Apr 2017

JINGCHENG LIU, ALISTAIR SINCLAIR, AND PIYUSH SRIVASTAVA

A b s tract. 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 β (the interaction) and
λ (the external field), except for the case |λ| = 1 (the “zero-field” case). A randomized algorithm (FPRAS)
for all graphs, and all β, λ, 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.

Jingcheng Liu, Computer Science Division, UC Berkeley. Email: liuexp@berkeley.edu.
Alistair Sinclair, Computer Science Division, UC Berkeley. Email: sinclair@cs.berkeley.edu.
Piyush Srivastava, Tata Institute of Fundamental Research, Mumbai. Email: piyush.srivastava@tifr.res.in.
JL and AS are supported in part by NSF grant CCF-1420934.

1.Introduction
The Ising model, first studied a century ago as a model for magnetic phase transitions by Lenz and
Ising [21], has since become an important tool for the modeling of interacting systems. In the Ising model,
such a system is represented as a graph G = (V, E), so that the individual entities comprising the system
correspond to the vertices V and their pairwise interactions to the edges E. A configuration of the system
is an assignment σ : V → {+, −} of one of two possible values (often called “spins”) to each vertex. The
model then induces a probability distribution (known as a Gibbs distribution) over these global configurations
in terms of local parameters that model the interactions of the vertices.
In our setting, it will be convenient to parameterize these interactions in terms of a vertex activity λ
(sometimes called an “external field”) that determines the propensity of a vertex to be in the + configuration,
and an edge activity β ≥ 0 that models the tendency of vertices to agree with their neighbors. The model
assigns to each configuration σ a weight
w(σ) := β |{{u,v}∈E | σ(u)6=σ(v)}| λ|{v | σ(v)=+}| = β |E (S,S )| λ|S| ,


where S = S(σ) is the set of vertices assigned spin + in σ and E S, S is the set of edges in the cut S, S
(i.e., the number of pairs of adjacent vertices assigned opposite spins). The probability of configuration
β
β
σ under the Gibbs distribution is then µ(σ) := w(σ)/ZG
(λ), where the normalizing factor ZG
(λ) is the
partition function defined as
X
X
β
(1)
ZG
(λ) :=
w(σ) =
β |E (S,S )| λ|S| .
S⊆V

σ:V →{+,−}

Notice that the partition function may be interpreted combinatorially as a cut generating polynomial in the
graph G.
In this paper we focus on the original ferromagnetic case in which β < 1, so that configurations in which
a larger number of neighboring spins agree (small cuts) have higher probability. The anti-ferromagnetic
regime β > 1 is qualitatively very different, and prefers configurations with disagreements between
neighbors. We note also that all our results in this paper hold in the more general setting where there is a
different interaction βe on each edge, provided that all the βe satisfy whatever constraints we are putting
on β. (So, e.g., in the ferromagnetic case βe < 1 for all e.) In addition, our results allow β to be negative
and λ to be complex; this will be discussed in more detail below.
As in almost all statistical physics and graphical models, the partition function captures the computational
complexity of the Ising model. Partition functions are #P-hard to compute in virtually any interesting case
(e.g., this is true for the Ising model except in the trivial cases λ = 0 or β ∈ {0, 1}), so attention is focused
on approximation. An early result in the field due to Jerrum and Sinclair [22] establishes a fully polynomial
randomized approximation scheme for the Ising partition function, valid for all graphs G and all values of
the parameters (β, λ) in the ferromagnetic regime. Like many of the first results on approximating partition
functions, this algorithm is based on random sampling and the Markov chain Monte Carlo method.
For several statistical physics models on bounded degree graphs (including the anti-ferromagnetic
Ising model [25, 41] and the “hard core”, or independent set model [45]), fully-polynomial deterministic
approximation schemes have since been developed, based on the decay of correlations property in those
models: roughly speaking, one can estimate the local contribution to the partition function at a given
vertex v by exhaustive enumeration in a neighborhood around v, using decay of correlations to truncate
the neighborhood at logarithmic diameter. The range of applicability of these algorithms is of course
limited to the regime in which decay of correlations holds, and indeed complementary results prove that
the partition function is NP-hard to approximate outside this regime [16, 42]. Perhaps surprisingly, however,
no deterministic approximation algorithm is known for the classical ferromagnetic Ising partition function
that works over anything close to the full range of the randomized algorithm of [22]: to the best of our
1

knowledge, the best deterministic algorithm, due to Zhang, Liang and Bai [47], is based on correlation
decay and is applicable to graphs of maximum degree ∆ only when β > (∆ − 1)/(∆ + 1).
The restricted applicability of correlation decay based algorithms for the ferromagnetic Ising model arises
from two related reasons: the first is that this model does not exhibit correlation decay for β sufficiently close
to 0 (for any given value of the external field), so any straightforward approach based only on this property
cannot be expected to work for all β. Secondly, there is a regime of parameters for which, even though
decay of correlation holds, there is evidence to believe that it cannot be exploited to give an algorithm using
the usual techniques: see [41, Appendix 2] for a more detailed discussion of this point.
The first goal of this paper is to supply such a deterministic algorithm which covers almost the entire
range of parameters of the model except for the “zero-field” case |λ| = 1:
Theorem 1.1. Fix any ∆ > 0. There is a fully polynomial time approximation scheme (FPTAS) for the Ising
β
partition function ZG
(λ) in all graphs G of maximum degree ∆ for all edge activities −1 ≤ β ≤ 1 and all
(possibly complex) vertex activities λ with |λ| =
6 1.
Remark. Note that although λ, β are positive in the “physically relevant” range in most applications of
the Ising model, the above theorem also applies more generally to β ∈ [−1, 1] and complex valued λ not
on the unit circle. Moreover, we can allow edge-dependent activities βe provided all of them lie in [−1, 1].
The above theorem is actually a special case of a more general theorem for the hypergraph version of
the Ising model (Theorem 1.3 below). We now illustrate our approach to proving these theorems, which
will also allow us to introduce and motivate our further results in the paper.
In contrast to previous algorithms based on correlation decay, our algorithm is based on isolating the
β
complex zeros of the partition function Z := ZG
(λ) (viewed as a polynomial in λ for a fixed value of β).
This approach was introduced recently by Barvinok [6, 7] in the context of models different from the Ising
model. We start with the observation that the 1 + ε multiplicative approximation of Z required for a
FPTAS corresponds to a O(ε) additive approximation of log Z. Barvinok’s approach considers a Taylor
expansion of log Z around a point λ0 such that Z(λ0 ) is easy to evaluate. (For the Ising model, λ0 = 0 is
such a choice.) It then seeks to evaluate the function at other points by carrying out an explicit analytic
continuation. More concretely, suppose it can be shown that there are no zeros of Z in the open disk
D(λ0 , r) of radius r around λ0 . From standard results in complex analysis, it then follows that the Taylor
expansion around λ0 of log Z is absolutely convergent in D(λ
 further, that the first k terms of this
 0 , r) and
k

0|
expansion evaluated at a point λ ∈ D(λ0 , r) provide a O |λ−λ
additive approximation of log Z(λ).
rk
We note that Barvinok’s approach may be seen as an algorithmic counterpart of the traditional view of
phase transitions in statistical physics in terms of analyticity of log Z [46].
To apply this approach in the case of the ferromagnetic Ising model, we may appeal to the famous
Lee-Yang theorem of the 1950s [24], which establishes that the zeros of Z(λ) all lie on the unit circle in the
complex plane. This allows us to take λ0 = 0 and r = 1 in the previous paragraph, and thus approximate
Z(λ) at any point λ satisfying |λ| < 1. This extends to all λ with |λ| =
6 1 via the fact that Z(λ) = λn Z( λ1 ).

Remark. We note that the case |λ| = 1 is likely to require additional ideas because it is known that there
β
exist bounded degree graphs (namely ∆-ary trees) for which the partition function ZG
(λ) has complex
zeros within distance O(1/n) of λ = 1, where n is the size of the graph. In fact, the zeros are even known
to become dense on the whole unit circle as n increases to infinity [4, 5]. This precludes the possibility of
efficiently carrying out the analytic continuation procedure for log Z to arbitrary points on the unit circle,
and to the point λ = 1 in particular.
Converting the above approach into an algorithm requires computing the first k coefficients in the Taylor
expansion of log Z around λ0 . Barvinok showed that this computation can in turn be reduced to computing
O(k) leading coefficients of the partition function itself. In the case of the Ising model, computing k
such coefficients is roughly analogous to computing k-wise correlations between the vertex spins, and
2

doing so naively on a graph of n vertices requires time Ω(nk ). Until recently, no better ways to perform
this calculation were known and hence approximation algorithms using this approach typically required
quasi-polynomial time in order to achieve a (1 + 1/ poly(n))-factor multiplicative approximation of Z
(equivalently, a 1/ poly(n) additive approximation of log Z), since this requires the Taylor series for log Z
to be evaluated to k = Ω(log n) terms [7–9].
Recently, Patel and Regts [35] proposed a way to get around this barrier for several classes of partition
functions. Their method is based on writing the coefficients in the Taylor series of log Z as linear combinations of counts of connected induced subgraphs of size up to Θ(log n). This is already promising, since the
number of connected induced subgraphs of size O(log n) of a graph G of maximum degree ∆ is polynomial
in the size of G when ∆ is a fixed constant. Further, the count of induced copies of such a subgraph can also
be computed in time polynomial in the size of G [14]. Patel and Regts built on these tools to show a way to
compute the Θ(log n) Taylor coefficients of log Z needed in Barvinok’s approach for several families of
partition functions, for some of which correlation decay based algorithms are still not known.
Unfortunately, for the case of the Ising model, it is not clear how to write the Taylor coefficients in terms
of induced subgraph counts. Indeed, in their paper [35, Theorem 1.4], Patel and Regts apply their method
to the Ising model viewed as a polynomial in β rather than λ, which allows them to use subgraph counts.
However, this prevents them from using the Lee-Yang theorem, and they are consequently able to establish
only a small zero-free region. As a result, they can handle only the zero-field “high-temperature” regime
(where in fact the correlation decay property also holds), specifically the regime |β − 1| ≤ 0.34/∆ and
λ = 1.
In this paper, we instead propose a generalization of the framework of Patel and Regts to objects that we
call insects. An insect is a graph in which each vertex is decorated with an additional number of dangling
“half edges” attached to it: we refer to section 3.1 for precise definitions. Using the appropriate notions for
counting induced sub-insects, we are then able to write the coefficients arising in the Taylor expansion
of log Z for the Ising model in terms of induced sub-insect counts, and derive from there algorithms for
computing Ω(log n) such coefficients in polynomial time in graphs of bounded degree. This establishes
Theorem 1.1. We note that if one is only interested in deriving Theorem 1.1, then this can also be done
using the notion of fragments, developed by Patel and Regts [35] in the different context of edge coloring
models, which turns out to be a special case of our notion of insects.
Our framework of insects, however, also allows us to extend the above approach to the more general
setting where G is a hypergraph (and further, when the edge activities are edge-dependent), as studied, for
example, in the work of Suzuki and Fisher [44]. We note that the Jerrum-Sinclair MCMC approach [22]
apparently does not extend to hypergraphs, and there is currently no known polynomial time approximation algorithm (even randomized) for a wide range of β in this setting. For a hypergraph H = (V, E),
β
configurations are again assignments of spins to the vertices V and the partition function ZH
(λ) is defined
exactly as in (1), where the cut E(S, S) consists of those hyperedges with at least one vertex in each of S
and S. The computation of coefficients via insects carries through as before, but the missing ingredient
is a extension of the Lee-Yang theorem to hypergraphs. Suzuki and Fisher [44] prove a weak version of
the Lee-Yang theorem for hypergraphs (see Theorem 4.3 in section 4), which we are able to strengthen to
obtain the following optimal statement, which is of independent interest:
Theorem 1.2. Let H = (V, E) be a hypergraph with maximum hyperedge size k ≥ 3. Then all the zeros
β
of the Ising model partition function ZH
(λ) lie on the unit circle if and only if the edge activity β lies in the
1
range − 2k−11 −1 ≤ β ≤ 2k−1 cosk−1
.
π
( k−1
)+1
Remark. Once again, we can allow edge-dependent activities βe provided all of them lie in the range
stipulated above. This extension also applies to Theorem 1.3 below.
Note that the classical Lee-Yang theorem (for the graph case k = 2) establishes this property for 0 ≤ β ≤ 1
(the ferromagnetic regime). Our proof of Theorem 1.2 follows along the lines of Asano’s inductive proof of
3

the Lee-Yang theorem [3], but we need to carefully analyze the base case (where H consists of a single
hyperedge) in order to obtain the above bounds on β. Since our analysis of the base case is tight, the range
of β in our theorem is optimal. For a detailed comparison with the Suzuki-Fisher theorem, see the Remark
following Corollary 4.5.
Combining Theorem 1.2 with our earlier algorithmic approach immediately yields the following generalization of Theorem 1.1 to hypergraphs.
β
Theorem 1.3. Fix any ∆ > 0 and k ≥ 3. There is an FPTAS for the Ising partition function ZH
(λ) in all
hypergraphs H of maximum degree ∆ and maximum edge size k, for all edge activities β in the range of
Theorem 1.2 and all vertex activities |λ| =
6 1.

Finally, we extend our results to general ferromagnetic two-spin systems on hypergraphs, again as
studied in [44]. A two-spin system on a hypergraph H = (V, E) is specified by hyperedge activities
ϕe : {+, −}|e| → C for e ∈ E, and a vertex activity ψ : {+, −} → C. (Note that we treat each hyperedge e
as a set of vertices.) Without loss of generality, we assume ϕe (−, · · · , −) = 1, and ψ(−) = 1, ψ(+) = λ.
Then the partition function is defined as:
X
Y
X
Y
Y

ϕ
(2)
ZH
(λ) :=
ϕe σ e
ψ(σ(v)) =
ϕe σ e λ|{v:σ(v)=+}| .
σ:V →{+,−} e∈E

v∈V

σ:V →{+,−} e∈E

We call a hypergraph two-spin system symmetric if ϕe (σ) = ϕe (−σ). Suzuki and Fisher [44] prove a
Lee-Yang theorem for symmetric hypergraph two-spin systems (which is weaker than our Theorem 1.2
above when specialized to the Ising model). Combining this with our general algorithmic approach yields
our final result:
Theorem 1.4. Fix any
P ∆ > 0 and k ≥ 2 and a family of symmetric edge activities ϕ = {ϕe } satisfying
ϕ
|ϕe (+, · · · , +)| ≥ 41 σ∈{+,−}V |ϕe (σ)|. Then there exists an FPTAS for the partition function ZH
(λ) of
the corresponding symmetric hypergraph two-spin system in all hypergraphs H of maximum degree ∆ and
maximum edge size k for all vertex activities λ ∈ C such that |λ| =
6 1.
The remainder of the paper is organized as follows. In section 2, we spell out Barvinok’s approach to
approximating partition functions using Taylor series. Section 3 introduces the notion of insects and shows
how to use them to efficiently compute the leading coefficients of the partition function in the general
context of hypergraphs; as discussed above, this machinery applied to graphs, in conjunction with the
Lee-Yang theorem, implies Theorem 1.1. Finally, in section 4 we prove our extension of the Lee-Yang
theorem to the hypergraph Ising model (Theorem 1.2), and then use it and the Suzuki-Fisher theorem to
prove our algorithmic results for hypergraphs, Theorems 1.3 and 1.4.
1.1. Related work. 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 dichotomy
theorems, which attempt to completely classify these problems as being either #P-hard or computable
(exactly) in FP (see, e.g., [15, 17]).
Since the problems are in fact #P-hard in most cases, algorithmic interest has focused largely on approximation, motivated also by the general observation that approximating the partition function is polynomial
time equivalent to sampling (approximately) from the underlying Gibbs distribution [23]. In fact, most early
approximation algorithms exploited this connection, and gave fully-polynomial randomized approximation
schemes (FPRAS) for the partition function using Markov chain Monte Carlo (MCMC) samplers for the Gibbs
distribution. In particular, for the ferromagnetic Ising model, the MCMC-based algorithm of Jerrum and
Sinclair [22] is valid for all positive real values of λ and for all graphs, irrespective of their vertex degrees.
(For the connection with random sampling in this case, see [36].) This was later extended to ferromagnetic
4

two-spin systems by Goldberg, Jerrum and Paterson [18]. Similar techniques have been applied recently to
the related random-cluster model by Guo and Jerrum [19].
Much detailed work has been done on MCMC for Ising spin configurations for several important classes
of graphs, including two-dimensional lattices (e.g., [28, 31, 32]), random graphs and graphs of bounded
degree (e.g., [34]), the complete graph (e.g., [26]) and trees (e.g., [10, 33]); we do not attempt to give a
comprehensive summary of this line of work here.
In the antiferromagnetic regime (β > 1), deterministic approximation algorithms based on correlation
decay have been remarkably successful for graphs of bounded degree. Specifically, for any fixed integer
∆ ≥ 3, techniques of Weitz [45] give a (deterministic) FPTAS for the antiferromagnetic Ising partition
function on graphs of maximum degree ∆ throughout a region R∆ in the (β, λ) plane (corresponding the
regime of “uniqueness of the Gibbs measure on the ∆-regular tree”) [25, 41]. A complementary result of
Sly and Sun [42] (see also [16]) shows that the problem is NP-hard outside R∆ . In contrast, no MCMC
based algorithms are known to provide an FPRAS for the anti-ferromagnetic Ising partition function
throughout R∆ . More recently, correlation decay techniques have been extended to obtain deterministic
approximation algorithms for the anti-ferromagnetic Ising partition function on hypergraphs over a range
of parameters [27], as well as to several other problems not related to the Ising model. In the ferromagnetic
setting, however, for reasons mentioned earlier, correlation decay techniques have had more limited success:
Zhang, Liang and Bai [47] handle only the “high-temperature” regime of the Ising model, while the recent
results for ferromagnetic two-spin systems of Guo and Lu [20] do not apply to the case of the Ising model.
In a parallel line of work, Barvinok initiated the study of Taylor approximation of the logarithm of the
partition function, which led to quasipolynomial time approximation algorithms [6–9]. More recently,
Patel and Regts [35] showed that for many models that can be written as induced subgraph sums, one can
actually obtain an FPTAS from this approach. In particular, for problems such as counting independent sets
with negative (or, more generally, complex valued) activities on bounded degree graphs, they were able
to match the range of applicability of existing algorithms based on correlation decay, and were also able
to extend the approach to Tutte polynomials and edge-coloring models (also known as Holant problems)
where little is known about correlation decay.
The Lee-Yang program was initiated by Lee and Yang [46] in connection with the analysis of phase
transitions. By proving the famous Lee-Yang circle theorem for the ferromagnetic Ising model [24], they
were able to conclude that there can be at most one phase transition for the model. Asano [3] extended the
Lee-Yang theorem to the Heisenberg model, and provided a simpler proof. Asano’s work was generalized
further by Suzuki and Fisher [44]. A complete characterization of Lee-Yang polynomials that are independent
of the “temperature” of the model was recently obtained by Ruelle [37]. The study of Lee-Yang type theorems
for other statistical physics models has also generated beautiful connections with other areas of mathematics.
For example, Shearer [39] and Scott and Sokal [38] established the close connection between the location of
the zeros of the independence polynomial and the Lovász Local Lemma, while the study of the zeros of
generalizations of the matching polynomial was used in the recent celebrated work of Marcus, Spielman
and Srivastava on the existence of Ramanujan graphs [29]. Such Lee-Yang theorems are exemplars of
the more general stability theory of polynomials [11, 12], a field of study that has had numerous recent
applications to theoretical computer science and combinatorics (see, e.g., [1, 2, 13, 29, 30, 40]).
2.A p p r ox i m at i o n o f t h e l o g - pa r t i t i o n f u n c t i o n b y Tay l o r s e r i e s
In this section we present an approach due to Barvinok [7] for approximating the partition function of a
physical system by truncating the Taylor series of its logarithm, as discussed in the introduction. We will
work in our most general setting of symmetric two-spin systems on hypergraphs, which of course includes
the Ising model (on graphs or hypergraphs) as a special case. As in (2), such a system has partition function
X
Y

ϕ
ZH
(λ) =
ϕe σ e λ|{v:σ(v)=+}| .
σ:V →{+,−} e∈E
5

ϕ
Our goal is a FPTAS for ZH
(λ), i.e., a deterministic algorithm that, given as input H, {ϕe }, λ with |λ| 6= 1
and ε ∈ (0, 1], runs in time polynomial in n = |H| and ε−1 and outputs a 1+ε multiplicative approximation
ϕ
of ZH
(λ), i.e., a number Ẑ satisfying
ϕ
ϕ
|Ẑ − ZH
(λ)| ≤ ε|ZH
(λ)|.

(3)

ϕ
(Note that in our setting Ẑ and ZH
(λ) may be complex numbers.)
ϕ
For fixed H and (hyper)edge activities ϕ, we will write Z(λ) = ZH
(λ) for short. By the symmetry
1
n
ϕe (σ) = ϕe (−σ), we have Z(λ) = λ Z( λ ). Thus without loss of generality we may assume |λ| < 1.
Letting f (λ) = log Z(λ), using the Taylor expansion around λ = 0 we get

f (λ) =

∞
X

f (j) (0) ·

j=0

λj
,
j!

where f (0) = log Z(0) = 0. Note that Z = exp(f ), and thus an additive error in f translates to a
multiplicative error in Z. More precisely, given ε ≤ 1/4, and f, fe ∈ C such that f − fe ≤ ε, we have
 


exp fe − exp(f ) = exp fe − f − 1 |exp(f )| ≤ 4ε |exp(f )| ,
where the last inequality, valid for ε ≤ 1/4, follows by elementary complex analysis. In other words, to
achieve a multiplicative approximation of Z within a factor 1 + ε, as required by a FPTAS, it suffices to
obtain an additive approximation of f within ε/4.
To get an additive approximation of f , we use the first m terms in the Taylor expansion. Specifically, we
P
(j) (0) · λj .
compute fm (λ) = m
j=0 f
j!
To compute f (j) (0), note that f 0 (λ) =

1 dZ(λ)
Z(λ) dλ ,

or

dZ(λ)
dλ

= f 0 (λ)Z(λ). Thus for any m ≥ 1,

m−1
X m − 1 dj
dm−j
dm
Z(λ)
=
Z(λ)
·
f (λ).
dλm
j
dλj
dλm−j

(4)

j=0

dj
Z(λ)
dλj
λ=0

for j = 0, · · · , m, eq. (4) is a non-degenerate (recall that Z(0) = 1) triangular

m
system of linear equations in f (j) (0) j=1 , which can be solved in O(m2 ) time.
om
n j
d
Z(λ)
We can now specify the algorithm: first compute dλ
; next, use the system in eq. (4) to
j
λ=0 j=0
 (j)
m
solve for f (0) j=1 ; and finally, compute and ouput the approximation fm (λ).
To quantify the approximation error in this algorithm, we need to study the locations of the complex
roots r1 , · · · , rn of Z. Throughout this paper, we will be using (some variant of) the Lee-Yang theorem to
argue that, for the range of interactions ϕ we are interested in, the
Q roots ri all lie on the unit circle in the
complex plane, i.e., |ri | = 1 for all i. Then we can write Z(λ) = i (1 − rλi ), and the log partition function
becomes

 X
 
n
n X
∞
X
1 λ j
λ
f (λ) = log Z =
log 1 −
=
.
ri
j ri
Given

i=1

Denoting the first m terms by fm (λ) =

i=1 j=1

Pn Pm
i=1

1
j=1 j

 j
λ
ri

, the error due to truncation is bounded by

∞
X
|λ|j
n |λ|m+1
|f (λ) − fm (λ)| ≤ n
≤
,
j
(m + 1)(1 − |λ|)
j=m+1
6

recalling that by symmetry we are assuming
|λ| < 1. Thus to get within ε/4 additive error, it suffices to

|λ|
1
take m ≥ 1−|λ| log(4n/ε) + log 1−|λ| . The following result summarizes our discussion so far.


n j
om
|λ|
d
1
log(4n/ε) + log 1−|λ|
, and the values of dλ
,
Lemma 2.1. Given 0 < ε < 1/4, m ≥ 1−|λ|
j Z(λ)
λ=0 j=0

fm (λ) can be computed in time poly(n/ε). Moreover, if the Lee-Yang theorem holds for the partition function
Z(λ), then |fm (λ) − f (λ)| < ε/4, and thus exp(fm (λ)) approximates Z(λ) within a multiplicative factor
1 + ε.
missingoingredient in turning Lemma 2.1 into an FPTAS is the computation of the derivatives
n The
m
dj
Z(λ)
, which themselves are just multiples of the leading coefficients of Z. Computing
dλj
λ=0 j=0

these values naively using the definition of Z(λ) requires nΩ(m) time. Since m is required to be of order
Ω(log(n/ε)), this results in only a quasi-polynomial time algorithm. In the next section, we show how
to compute these values in polynomial time when H is a hypergraph of bounded degree and bounded
hyperedge size, which when combined with Lemma 2.1 gives an FPTAS.
3.Computing coefficients via insects
As discussed in the introduction, Patel and Regts [35] recently introduced a technique for efficiently
computing the leading coefficients of a partition function using induced subgraph counts. In this section
we introduce the notion of sub-insect counts, and show how it allows the Patel-Regts framework to be
adapted to any hypergraph two-spin system with vertex activities (including the Ising model with vertex
activities as a special case). We will align our notation with [35] as much as possible. From now on, unless
otherwise stated, we will use G to denote a hypergraph. Recall from the introduction the partition function
of a two-spin system on a hypergraph G = (V, E):
X
Y

ϕ
(5)
ZG
(λ) =
ϕe σ e λ|{v:σ(v)=+}| .
σ:V →{+,−} e∈E

Due to the normalization ϕe (−, · · · , −) = 1, each term in the summation depends only on the set
S = {v : σ(v) = +} and the labelled
S induced sub-hypergraph S ∪ ∂S, E[S] ∪ E(S, S̄) , where ∂S is the
boundary of S defined as ∂S := v∈S NG (v) \ S and NG (v) is the set of vertices adjacent to the vertex v
in G. This fact motivates the induced sub-structures we will consider.
Let σ S be the configuration where the set of vertices assigned +-spins is S, that is, σ S (v) = + for
v ∈ S and σ S (v) = − otherwise. We will also write ϕe (S) := ϕe (σ S e ) for simplicity. Thus the partition
function can be written
X Y
ϕ
ZG
(λ) =
ϕe (S)λ|S| .
S⊆V e:e∩S6=∅

We start with the standard factorization of the partition function in terms of its complex zeros r1 , . . . , rn ,
where n = |V |. Since we are assuming ϕe (−, · · · , −) = 1, the product of the zeros is 1. The partition
function can then be written as
n
Y
X
ϕ
ZG
(λ) =
(1 − λ/ri ) =
(−1)i ei (G)λi ,
i

i=0

where ei (G) is the elementary symmetric polynomial evaluated at ( r11 , · · · , r1n ).
On the other hand, we can also express the coefficients ei (G) combinatorially using the definition of the
partition function:
X Y
(6)
ei (G) = (−1)i
ϕe (S).
S⊆V e:e∩S6=∅
|S|=i
7

Oncewe have computed
the first m coefficients of Z (i.e., the values ei (G) for i = 1, · · · , m), where

|λ|
m = Ω 1−|λ| log(n/ε) , we can use Lemma 2.1 to obtain an FPTAS as claimed in Theorems 1.1, 1.3 and 1.4.
The main result in this section will be an algorithm for computing these coefficients ei (G):
Theorem 3.1. Let C > 0, ∆ ∈ N. Given an n-vertex hypergraph G of maximum degree ∆, maximum
hyperedge size k, then for any ε > 0 there exists a deterministic poly(n/ε)-time algorithm to compute ei (G)
for i = 1, · · · , m, where m = dC log(n/ε)e.
3.1. Insects in a hypergraph. To take advantage of the fact that each term in eq. (5) only depends on the
set S and the induced sub-hypergraph S ∪ ∂S, E[S] ∪ E(S, S̄) , we define the following structure.
Definition 3.2. For disjoint sets S and B, an insect H = (S, E, B) is a labelled hypergraph (S ∪ B, E)
such that each vertex in B is incident on exactly one hyperedge in E. The set S is called the label set of the
insect H and the set B the boundary set.
Given an insect H, we use the notation V (H) for its label set. The size |H| of the insect H is defined to
be |V (H)|. H is said to be connected if the induced sub-hypergraph on the label set V (H) is connected.
Remark. Note that a hypergraph G = (V, E) can itself be viewed as the insect (V, E, ∅).
In order to exploit the structure of the terms in eq. (5) alluded to above, we now define the notion of
an induced sub-insect of an insect. Given an insect H = (S, E, B) and a subset S 0 of S, we define ∂ + S 0
as follows: starting with ∂S 0 , for each vertex v ∈ ∂S 0 , if v is incident on d hyperedges in E(S 0 , S̄ 0 ), we
replace v with d copies of itself labelled v (1) , · · · , v (d) , one for each of the hyperedges in lexicographic
order, so that each v (i) is incident on only one hyperedge. Denote the set of these new hyperedges by E 0 .
The induced sub-insect H + [S 0 ] is then defined as (S 0 , E[S 0 ] ∪ E 0 , ∂ + S 0 ). Note that if S 0 = ∅, then H + [S 0 ]
is the empty graph.
3.1.1. Weighted sub-insect counts. Just as graph invariants may be expressed asP
sums over induced subgraph counts, we will consider weighted sub-insect counts of the form f (G) = S⊆V (G) aG+ [S] and the
functions f expressible in this way.
Let Gt∆,k be the set of insects up to size t, with maximum degree ∆ and maximum hyperedge size k.
Note that since insects are labelled, this is an infinite set. We will fix ∆ and k throughout, and write
S
G := t≥1 Gt∆,k . Let w(H, G) be the indicator that H is an induced sub-insect of G, that is,
w(H, G) = 1 if and only if there is a set S ⊆ V (G) such that G+ [S] = H.
A
Pweighted sub-insect count f (G) of the form considered above can then also be written as f (G) =
H∈G aH w(H, G). Note that even though G is infinite, the above sum has only finitely many non-zero
terms for any finite insect G. It is also worth noting that, as insects are labelled, f (G) may also depend on
the labelling of G, unlike a graph invariant where isomorphic copies of a graph are the same.
3.2. Properties of weighted sub-insect counts. A weighted sub-insect count f is said to be additive if,
given any two disjoint insects G1 and G2 , f (G1 ] G2 ) = f (G1 ) + f (G2 ). Analogously to the case of graph
invariants, we then have the following:
Lemma 3.3. Let f be a weighted sub-insect count, so that f may be written as
X
X
f (G) :=
aG+ [S] =
aH · w(H, G).
S⊆V

H∈G

Then f is additive if and only if aH = 0 for all insects H that are disconnected.
8

Proof. When H is connected, we have w(H, G1 ] G2 ) = w(H, G1 ) + w(H, G2 ); thus f given in the above
form is additive if aH 0 = 0 for all H 0 that are not connected.
Conversely, suppose f is additive. By the last paragraph, we can assume without loss of generality that
the sequence aH is supported on disconnected insects (by subtracting the component of f supported on
connected H). We now show that for such an f , aH must be 0 for all disconnected H as well.
For if not, then given an f with aH 0 = 0 for all connected insects H 0 , let H be an insect with the smallest
size for which aH 6= 0. If H has only one vertex, then it is vacuously connected and hence aH = 0, so we
already have a contradiction. Otherwise, we know that aJ = 0 for all insects J which have strictly fewer
vertices than H. Since w(H, J) = 0 when the number of vertices in J is strictly smaller than in H, this
also implies that f (J) = 0 for any graph J that is strictly smaller in size than H.
Since H is disconnected, there exist non-empty insects H1 and H2 such that H = H1 ] H2 . By additivity,
we then have f (H) = f (H1 ) + f (H2 ) = 0, where the last equality follows since both H1 and H2 are
strictly smaller than H. On the other hand, since H is an insect with the smallest possible number of
vertices such that aH 6= 0, we also have f (H) = aH w(H, H) = aH . This implies aH = 0, which is a
contradiction.

Our next lemma implies that products of weighted sub-insect counts can also be expressed as a weighted
sub-insect count of slightly larger insects:
Lemma 3.4. Let H1 = (S1 , E1 , B1 ), H2 = (S2 , E2 , B2 ) be arbitrary insects. Either for every G we have
w(H1 , G)w(H2 , G) = 0,
or there exist a set S 0 ⊇ S1 ∪ S2 , a set B 0 disjoint from S 0 , and an insect H = (S 0 , E 0 , B 0 ) such that
H + [S1 ] = H1 , H + [S2 ] = H2 , and for every G we have
w(H1 , G)w(H2 , G) = w(H, G).

(7)

Before proving this lemma, we define a notion of compatibility for insects.
Definition 3.5. An insect H1 = (S1 , E1 , B1 ) is compatible with another insect H2 = (S2 , E2 , B2 ) if
H1+ [S1 ∩ S2 ] = H2+ [S1 ∩ S2 ].
Observation 3.6. When H1 and H2 are compatible, there exists a unique insect H (which we denote by
H1 ∪ H2 by a slight abuse of notation) with label set V (H1 ) ∪ V (H2 ) such that H + [V (H1 )] = H1 and
H + [V (H2 )] = H2 .
We now proceed with the proof of Lemma 3.4.
Proof of Lemma 3.4. If H1 is not compatible with H2 , then for every G, either H1 is an induced sub-insect
of G, or H2 is, but not both. Thus w(H1 , G)w(H2 , G) = 0.
If H1 and H2 are compatible, then let H = H1 ∪ H2 be the insect promised by Observation 3.6. We have
X X
 

w(H1 , G)w(H2 , G) =
G+ [T1 ] = H1 · G+ [T2 ] = H2
T1 ⊆V T2 ⊆V

=

X X X

 

G+ [T1 ] = H1 · G+ [T2 ] = H2 · [T = T1 ∪ T2 ]

T ⊆V T1 ⊆V T2 ⊆V

=

X

G+ [T ] = H1 ∪ H2 , using the definition of compatibility
T ⊆V

= w(H, G).


9

3.3. Enumerating connected sub-insects. Our goal is to show that ei (G) defined in eq. (6) can be
written as a weighted sub-insect count. Recall that we denote by Gt∆,k the set of distinct induced sub-insects
of G up to t vertices with maximum degree ∆ and maximum hyperedge size k. We then have
X Y
X
(8)
ei (G) = (−1)i
ϕe (S) =
λH,i · w(H, G),
S⊆V e:e∩S6=∅
|S|=i

where λH,i = (−1)i

Q

e:e∩SH 6=∅ ϕe (SH )

H∈Gi∆,k
H=(VH ,EH ,SH )

if |H| = i, and 0 otherwise. Note that λH,i is easily computable in

time poly(|H| ); however, as discussed in the introduction, the number of H ∈ Gi∆,k such that w(H, G) 6= 0
will be Ω(ni ), and a naive computation of ei (G) using eq. (8) would be inefficient. To prove Theorem 3.1,
we consider the set of connected insects, denoted by Ci∆,k , instead of Gi∆,k . We will show in this subsection
that Ci∆,k can be efficiently enumerated, and then in the following subsection reduce the above summation
over Gi∆,k to enumerations of Ci∆,k .
Following Patel and Regts [35], we use the following result based on Borgs, Chayes, Kahn and Lovász [14,
Lemma 2.1 (c)].
Lemma 3.7. Let G be a multigraph with maximum degree ∆ (counting edge multiplicity) and let v ∈ V (G).
t−1
Then the number of subtrees of G with t vertices containing the vertex v is at most (e∆)2 .
Proof. Consider the infinite rooted ∆-ary tree T∆ . The number of subtrees with t vertices starting from the
 (e∆)t−1
t∆
root is 1t t−1
<
. (See also [43, Theorem 5.3.10].)
2
Next note that every subtree of the multigraph G containing the vertex v, induces injectively a subtree of
t−1
T∆ containing the root. Thus the number of subtrees of G containing vertex v is also at most (e∆)2 . 
Corollary 3.8. Let G be a hypergraph with maximum degree ∆ and maximum hyperedge size k, and let
v ∈ V (G). Then the number of connected induced sub-insects of G with t vertices containing the vertex v is at
t−1
.
most (e∆k)
2
Proof. Consider the multigraph H obtained by replacing every hyperedge of size r in G by an r-clique. For
any two distinct connected induced sub-insects A and B, let SA and SB be their sets of spanning trees.
Then since the label sets of A and B are different, SA ∩ SB = ∅. Thus the number of connected subtrees is
an upperbound on the number of connected induced sub-insects.
In this multigraph the maximum degree is ∆k, so by Lemma 3.7 the number of subtrees is at most
(e∆k)t−1
. Thus the number of connected induced sub-insects of G with t vertices containing the vertex v is
2
also at most

(e∆k)t−1
.
2



As a consequence we can efficiently enumerate all connected induced sub-insects of logarithmic size in a
bounded degree graph. This follows from a similar reduction to a multigraph, and then applying [35, Lemma
3.4]. However, for the sake of completeness we also include a direct proof.
Lemma 3.9. For a hypergraph of maximum degree ∆ and maximum hyperedge size k, there exists an efficient
e 3 (e∆k)t+2 ). Here O
e hides factors
enumerator for connected induced sub-insects of size t, that runs in time O(nt
of the form polylog(n) , polylog(∆k) and polylog(t).
Proof. Let Tt be the set of S ⊆ V (G) such that |S| ≤ t and G[S] is connected. Note that given S ∈ Tt ,
G+ [S] will be a sub-insect of size t, and this clearly enumerates all of them. Also by Corollary 3.8,
|Tt | ≤ O(n(e∆k)t ). Thus it remains to give an algorithm to construct Tt in about the same amount of time.
We construct Tt inductively. For t = 1, T1 := V (G). Then given Tt−1 , let
Tt∗ := Tt−1 ∪ {S ∪ {v} : S ∈ Tt−1 and v ∈ NG (S) \ S} .
10

Since |NG (S)| < t∆k, thus one can compute the set NG (S) \ S in time O(t∆k), and construct Tt∗ in time
O(|Tt−1 | t∆k) = O(nt(e∆k)t+1 ). Finally we remove duplicates in Tt∗ to get Tt (e.g., by sorting the sets
e
e 3 (e∆k)t+1 ).
S ∈ Tt∗ , where each can be represented by a string of length O(t)),
in time O(nt
Starting from T1 , inductively we perform t iterations to construct Tt . Thus the overall running time is
Pt e 3
i+1 ) = O(nt
e 3 (e∆k)t+2 ).

i=1 O(ni (e∆k)
3.4. Proof of Theorem 3.1. The previous subsection allows us to efficiently enumerate connected subinsects. To prove Theorem 3.1, it remains to reduce the sum over all (possibly disconnected) H in eq. (8) to
a sum over connected H. Consider the t-th power sum:
pt =

n
X
1
.
rit
i=1

Now by Newton’s identities (which relate power sums to elementary symmetric polynomials), we have
(9)

pt =

t−1
X
(−1)i−1 pt−i ei + (−1)t−1 tet .
i=1

Recall from eq. (8) that ei is a weighted sub-insect count, and also from Lemma 3.4 that the product of
weighted sub-insect counts is also a weighted sub-insect count. Therefore, pk is also a weighted sub-insect
count:
X
(10)
pt (G) =
aH,t w(H, G),
H∈Gt∆,k

for some aH,t to be determined.
Next note that ZG1 ]G2 (λ) = ZG1 (λ) · ZG2 (λ) is multiplicative, and hence the t-th power sum pt is
additive. Hence by Lemma 3.3, its coefficients are supported on connected insects:
X
(11)
pt (G) =
aH,t w(H, G),
H∈Ct∆,k

where Ct∆,k is the set of distinct connected sub-insects with up to t vertices and maximum degree ∆,
maximum hyperedge size k. Notice that by Corollary 3.8, there are at most n(e∆k)t non-zero terms (where
w(H, G) 6= 0).
Now we show how to compute the coefficients aH,t efficiently, following the same approach as in [35,
Lemma 3.6].
Lemma 3.10. There is a poly(n/ε)-time algorithm to compute all the coefficients aH,t in eq. (11), for
t ≤ O(log(n/ε)).
Proof. By Lemma 3.9, we compute Tt , consisting of all S ⊆ V (G) such that |S| ≤ t and G[S] is connected.
As we have removed duplicates, this is exactly Ct∆,k .
By eq. (9), for t = 1 we have p1 = e1 , so by eq. (8) we can read off the coefficients aH,1 from e1 (G). Next
suppose we have computed aH 0 ,t0 for |H 0 | ≤ t0 < t, and we want to compute aH,t for fixed H. Again by
Newton’s identities, it suffices to compute the coefficients of w(H, G) in pt−i ei . By eqs. (7), (8) and (11),
the coefficient of w(H, G) in pt−i ei is given by:
X
X
(12)
aH2 ,(t−i) λH1 ,i =
aH[S2 ],(t−i) λH[S1 ],i .
H1 ∈Gi ,H2 ∈C(t−i)
H1 compatible with H2
H1 ∪H2 =H

(S1 ,S2 )
S1 ∪S2 =V (H)

Since t ≤ O(log(n/ε)), the second sum involves at most 4t = poly(n/ε) terms. Moreover, due to Corollary 3.8, there are at most tn(e∆k)t = poly(n/ε) previously computed aH 0 ,t0 , where H 0 is a connected
11

sub-insect of G and |H 0 | ≤ t0 < t. And to look up aH[T ],(t−i) , one can do a linear scan, which also takes
time poly(n/ε) for t ≤ O(log(n/ε)).
To conclude, because t ≤ O(log(n/ε)), eq. (11) only contains poly(n/ε) terms. And for each term, aH,t
can be computed using the above dynamic programming scheme in poly(n/ε) time.

Finally, now that we can compute aH,t efficiently, by eq. (11) we can compute pk using the sub-insect
enumerator in Lemma 3.9, and we can then compute ek using Newton’s identities as in eq. (9), which
completes the proof of Theorem 3.1.
3.5. Proofs of main theorems. Our first main result in the introduction, the FPTAS for the Ising model
on graphs throughout the ferromagnetic regime with non-zero field stated in Theorem 1.1, now follows by
combining Theorem 3.1 with Lemma 2.1 and the Lee-Yang theorem [24] (also stated as Theorem 4.2 in the
next section). Recall from the introduction that the Lee-Yang theorem ensures that the partition function
has no zeros inside the unit disk.
Similarly, Theorem 1.4, the FPTAS for two-spin systems on hypergraphs, follows by combining Theorem 3.1 with Lemma 2.1 and the Suzuki-Fisher theorem [44] (also stated as Theorem 4.3 in the next section).
Again, the Suzuki-Fisher theorem ensures that there are no zeros inside the unit disk, under the condition
on the hyperedge activities stated in Theorem 1.4.
To establish our final main algorithmic result, Theorem 1.3, we first need to prove a new Lee-Yang
theorem for the hypergraph Ising model as stated in Theorem 1.2 in the introduction. This will be the
content of the next and final section of our paper. Once we have that, Theorem 1.3 follows immediately by
the same route as above.
4 . A L e e - Ya n g T h e o r e m f o r H y p e r g r a p h s
In this section we prove a tight Lee-Yang theorem for the hypergraph Ising model (Theorem 1.2 in the
introduction). We start by extending the definition of the hypergraph Ising model to the multivariate
setting, where each vertex and each hyperedge is allowed to have a different activity. As before, we have
an underlying hypergraph G = (V, E) with |V | = n vertices. Given vertex activities λ1 , λ2 , . . . , λn and
hyperedge activities β = (βe ), we define
X Y
Y
β
ZG
(λ1 , · · · , λn ) =
βe
λi ,
S⊆V e∈E (S,S )
i∈S
where for a subset S ⊆ V , E(S, S) is the set of hyperedges with at least one vertex in each of S and S.
Note that


n
Y
1
1
β
β
(13)
ZG (λ1 , · · · , λn ) =
λi · ZG
,··· ,
.
λ1
λn
i=1

We recall the definition of the Lee-Yang property (see, e.g., [37]).
Definition 4.1 (Lee-Yang property). Let P (z1 , z2 , . . . , zn ) be a multilinear polynomial with real coefficients. P is said to have the Lee-Yang property (sometimes written as “P is LY”) if for any complex numbers
λ1 , · · · , λn such that |λ1 | ≥ 1, · · · , |λn | ≥ 1, and |λi | > 1 for some i, it holds that P (λ1 , · · · , λn ) 6= 0.
Then the seminal Lee-Yang theorem [24] can be stated as follows:
Theorem 4.2. Let G be a connected undirected graph, and suppose 0 < β < 1. Then the Ising partition
β
function ZG
(λ1 , · · · , λn ) has the Lee-Yang property.
The following extension of the Lee-Yang theorem to general two-spin systems on hypergraphs is due
to Suzuki and Fisher [44]. Again the theorem is stated in the multivariate setting, where in the two-spin
partition function in eq. (5) each vertex i has a distinct activity λi .
12

Theorem 4.3. Consider any symmetric hypergraph two-spin system, with a connected hypergraph G and edge
ϕ
interactions {ϕe }. Then the partition function ZG
(λ1 , · · · , λn ) has the Lee-Yang property if |ϕe (+, · · · , +)| ≥
P
1
4
σ∈{+,−}V |ϕe (σ)| for every hyperedge e.
Theorem 4.3 is not tight for the important special case of the Ising model on hypergraphs. Our goal in
this section is to prove a tight analog of the original Lee-Yang theorem for this case. Specifically, we will
prove the following:
Theorem 4.4. Let G = (V, E) be a connected hypergraph, and β = (βe )e∈E be the vector of real valued
β
hyperedge activities so that the activity of edge e ∈ E is βe . Then ZG
has the Lee-Yang property if and only if
the following condition holds for every hyperedge e: let k > 1 be the size of e,
• if k = 2, then −1 < βe < 1;
1
.
• if k ≥ 3, then − 2k−11 −1 < βe < 2k−1 cosk−1
π
)+1
( k−1
Note that the case k = 2 is just the original Lee-Yang theorem (Theorem 4.2).
β
The following corollary for the univariate polynomial ZG
(λ) follows immediately via eq. (13) and the
β
fact that, by Hurwitz’s theorem, the zeros of ZG (λ) are continuous functions of β and thus remain on the
unit circle after taking the limit in the range of each βe .
Corollary 4.5. Let G = (V, E) be a connected hypergraph, and β = (βe )e∈E be the vector of real valued
hyperedge activities so that the activity of edge e ∈ E is βe . Then, all complex zeros of the univariate partition
β
function ZG
(λ) lie on the unit circle if and only if the following condition holds for every hyperedge e: let
k > 1 be the size of e,
• if k = 2, then −1 ≤ βe ≤ 1;
1
• if k ≥ 3, then − 2k−11 −1 ≤ βe ≤ 2k−1 cosk−1
.
π
)+1
( k−1
This establishes Theorem 1.2 in the introduction, and hence also Theorem 1.3 as explained at the end of
the previous section.
Remark. As a comparison, the Suzuki and Fisher result, which we restated in Theorem 4.3, implies that a
β
sufficient condition for the Lee-Yang property of ZG
(λ) is
1
1
≤ βe ≤ k−1
.
2k−1 − 1
2
−1
Note that while the lower bound on βe is the same as ours, our (tight) upper bound is always better, and
significantly so for the more interesting case of small k. E.g., for k = 3, our result gives the optimal range
− 31 ≤ βe ≤ 1, while the Suzuki-Fisher theorem gives − 13 ≤ βe ≤ 31 . Similarly, for k = 4, the respective
ranges are [−1/7, 1/2] (for ours) and [−1/7, 1/7] (for Suzuki-Fisher).
−

We turn now to the proof of Theorem 4.4. We will make use of the following criterion for the Lee-Yang
property.
Lemma 4.6. Given a multilinear polynomial P (z1 , z2 , . . . , zn ) with real coefficients define, for each 1 ≤ j ≤
n, multilinear polynomials Aj and Bj in the variables z1 , . . . , zj−1 , zj+1 , . . . , zn such that
P = Aj z j + B j
If P has the Lee-Yang property then, for every j such that the variable zj has positive degree in P , it holds that
Aj (z1 , . . . , zj−1 , zj+1 , . . . , zn ) 6= 0 when |zi | ≥ 1 for all i 6= j. In particular, Aj itself is LY.
Proof. Without loss of generality, we assume that j = 1. Note that since z1 has positive degree in P , A1
is a non-zero polynomial. Suppose that, in contradiction of the claim of the lemma, there exist complex
numbers λ2 , . . . , λn satisfying |λi | ≥ 1 such that A1 (λ2 , . . . , λn ) = 0. Since P is LY, it follows that
13

B1 (λ2 , . . . , λn ) 6= 0 (for otherwise, we get a contradiction to the Lee-Yang property by choosing z1 to be
an arbitrary value outside the closed unit disk).
By continuity, this implies that |B1 | is positive in any small enough neighborhood of (λ2 , . . . , λn ) in
n−1
C
. In particular, let S be the open set
S := {(y2 , . . . , yn ) | |yi − λi | <  and |yi | > 1 for 2 ≤ i ≤ n } .
Then there exist positive δ0 and 0 such that |B1 | is at least δ0 in the open set S when  < 0 .
Now, since A1 is a non-zero multilinear polynomial, it cannot vanish identically on any open set. In particular, it cannot vanish identically in S for any  > 0. On the other hand, since A1 vanishes at (λ2 , . . . , λn )
it follows from continuity that for  < 0 small enough, |A1 | ≤ δ0 /2 in S . Since A1 does not vanish identically on S , there must exist a point (y2 , . . . , yn ) in S such that 0 < |A1 (y1 , y2 , . . . , yn )| < δ0 /2. Since
|B1 (y2 , . . . , yn )| ≥ δ0 by the choice of 0 , it follows that if we define y1 = −B1 (y2 , . . . , yn )/A1 (y2 , . . . , yn )
then 2 < |y1 | < ∞. However, we then have P (y1 , y2 , . . . , yn ) = 0 even though |y1 | > 1 and |yi | ≥ 1 for
all i. This contradicts the Lee-Yang property of P .

By iterating the above lemma, we get the following corollary.
Corollary 4.7. Let P (z1 , z2 , . . . , zn ) be a multilinear polynomial with non-zero coefficients, i.e.,
X
Y
P (z1 , . . . , zn ) =
pS
zi ,
S⊆[n]

i∈S

where pS 6= 0 for all ⊆ [n]. Then, for every subset S of [n], the polynomial AS defined by the equation
Y
X
Y
P (z1 , . . . , zn ) = AS ((zi )i6∈S )
zi +
pT
zi
i∈S

T )S

i∈T

has the property that AS ((zi )i6∈S ) 6= 0 when |zi | ≥ 1 for all i 6∈ S. In particular, A is LY.
We next show that Lemma 4.6 has a partial converse for symmetric multilinear functions.
Lemma 4.8. Let P (z1 , z2 , . . . , zn ) be a symmetric multilinear polynomial with non-zero real coefficients, i.e.,
X
Y
P (z1 , . . . , zn ) =
pS
zi ,
S⊆[n]

i∈S

where pS 6= 0 for all ⊆ [n] and pS = pS . Assume further that the polynomials Aj as defined in Lemma 4.6 all
have the property that they are non-zero when all their arguments zi satisfy |zi | ≥ 1. Then P is LY.
Proof. We first show that, under our assumptions, if all but one of the zj lie on the unit circle, then P can
only vanish if the remaining zj is also on the unit circle. Without loss of generality we set j = 1, that is, we
will show that if |zi | = 1 for i ≥ 2, then any root z1 = ζ1 in the equation A1 z1 + B1 = 0 satisfies |ζ1 | = 1.
(Here A1 and BP
1 are in the notation
Q of Lemma 4.6.)
Since A1 = S⊆[2,n] pS∪{1} i∈S zi does not vanish with this setting of the zi , we have
Q

P
P
Q
i6∈S (1/zi )
S⊆[2,n] pS
Y
p
z
B1
S⊆[2,n] S
i∈S i
i6=1


Q
Q
=
zi P
|ζ1 | =
= P
A1
S⊆[2,n] pS∪[1]
i∈S zi
S⊆[2,n] pS∪[1]
i∈S zi
i∈[2,n]
Q
P
P
Q
i6∈S zi
S⊆[2,n] pS
(?)
(†)
S⊆[2,n] pS∪[1]
i∈S zi
i6=1
Q
Q
= P
(14)
= P
= 1.
S⊆[2,n] pS∪[1]
i∈S zi
S⊆[2,n] pS∪[1]
i∈S zi
Here (?) uses the fact that |zi | = 1 for i ≥ 2 and (†) uses the symmetry of P . We have thus shown that if
(z1 , z2 , . . . , zn ) is a zero of P such that |zi | ≥ 1 for all i then it is impossible for only one zi to lie outside
the closed unit disk.
14

We now show that if there are k ≥ 2 values of i for which zi lies outside the closed unit disk, then we can
find another zero (ζ1 , ζ2 , ζ3 , . . . , ζn ) of P such that |ζi | ≥ 1 for all i, and exactly k − 1 of the ζi lie outside
the closed open disk. We can then iterate this process to reduce k to 1, in which case the observation in the
previous paragraph leads to a contradiction.
By re-numbering the indices if needed, we can assume that |z1 | , |z2 | > 1 and |zi | ≥ 1 for i ≥ 3. We can
then write
P (z1 , . . . , zn ) = α12 z1 z2 + α1 z1 + α2 z2 + α∅ ,
where α12 , α1 , α2 and α∅ are non-zero polynomials in z3 , . . . , zn . Further, the hypotheses of the lemma
imply that A1 = α12 z2 + α1 and A2 = α12 z1 + α2 both have the Lee-Yang property. Thus, by Lemma 4.6,
α12 (z3 , . . . , zn ) 6= 0, whence |zi | ≥ 1 for i ≥ 3. Now, A2 6= 0 when |z1 | and |z3 | , . . . , |zn | are at least 1,
2 (z3 ,...,zn )
while z1 = αα12
(z3 ,...,zn ) gives A2 = 0. Thus, we must have that
|α2 (z3 , . . . , zn )|
< 1 when |zi | ≥ 1 for i ≥ 3.
|α12 (z3 , . . . , zn )|

(15)

We now set ζi = zi for i ≥ 3, and consider z1 as a function of z2 . The equality P (z1 , z2 , ζ3 , . . . , ζn ) = 0 is
now equivalent to
z1 = −

(16)

α2 z 2 + α∅
.
α12 z2 + α1

Further, the hypotheses of the lemma imply that the denominator (which is A1 (z2 , ζ3 , . . . , ζn )) is non-zero
when |z2 | ≥ 1. We thus see that
|α2 |
< 1.
|α12 |

lim |z1 | =

(17)

z2 →∞

Initially, both z1 and z2 lie outside the closed unit disk. Thus, by eq. (17) and continuity, we can take z2
large enough in absolute value such that z1 as defined in eq. (16) lies on the unit circle. We now choose
ζ1 and ζ2 to be these values of z1 and z2 respectively, so that we have P (ζ1 , . . . , ζn ) = 0 and the number
of the ζi lying on the unit circle is exactly one less than the number of the zi lying on the unit circle, as
required.

The first step in our proof of Theorem 4.4 is to derive conditions under which the Ising partition function
of a hypergraph consisting of a single hyperedge has the Lee-Yang property; it will turn out that this is
actually the determining case for the full theorem. We will require the following technical lemma.
Lemma 4.9. Let m be any integer, and k a positive integer such that 2 |m| ≤ k. Consider the maximization
problem
max

k
Y

cos θi

i=1

π
π
≤ θi ≤ ,
2
2
k
X
θi = mπ.

subject to −

i=1

The maximum is cosk


mπ
k

, and is attained when θi =

π
k

for all i.

Proof. We can assume without loss of generality that θi ∈ (−π/2, π/2) at any maximum (for otherwise
the objective value is 0). Now, consider the function f (x) = log cos x defined on the interval (−π/2, π/2).
15

Since f 0 (x) = − tan x is a decreasing function, f (x) is concave for x ∈ (− π2 , π2 ). Thus by Jensen’s
inequality,
!
Pk
k
k
 mπ 
Y
X
i=1 θi
log
cos θi =
f (θi ) ≤ kf
≤ k log cos
,
k
k
i=1

and equality holds when θi =

i=1

mπ
k

for all i. Note that these θi are in (−π/2, π/2) since 2 |m| ≤ k.



We are now ready to tackle the case of a single hyperedge.
Lemma 4.10. Fix an integer k ≥ 2 and a hyperedge activity β ∈ R. Let G = (V = {v1 , v2 , . . . , vk } , E =
{{v1 , v2 , . . . , vk }}) be a hypergraph consisting of a single hyperedge of size k and activity β. If k = 2 and
β ∈ (−1, 1), or k ≥ 3 and β satisfies
−

1
2k−1

−1

1

<β<

2k−1 cosk−1



π
k−1



,
+1

β
has the Lee-Yang property.
then the partition function ZG

Remark. Note that the condition on β imposed above is monotone in k: i.e., if β is such that the partition
function of a hyperedge of size k ≥ 2 is LY, then for the same β the partition function of a hyperedge of
size k 0 < k is also LY.
Proof. For k = 2, the lemma is a special case of the Lee-Yang theorem [24] (although it also follows by
specializing the argument below). We therefore assume k ≥ 3.
Since the Ising partition function is symmetric and all terms in the polynomial appear with positive
coefficients, Lemma 4.8 applies and it suffices to verify that the coefficients Aj do not vanish when |zi | ≥ 1
for i 6= j. Without loss of generality we fix j = 1. We then have,
A1 = β

k
Y

(1 + zi ) + (1 − β)

i=1
i6=j

k
Y

zi .

i=1
i6=j

Thus A1 = 0 for |zi | ≥ 1 is equivalent to
(18)


k 
Y
1
1
=1−
1+
.
β
zi
i=1
i6=j

To establish the lemma, we therefore only need to show that for the claimed values of β, eq. (18) has no
solutions when |zi | ≥ 1 for all i ≥ 2. We now proceed to establish this by analyzing the product on the
right hand side of eq. (18).
The map z 7→ 1 + 1/z is a bijection from the complement of the open unit disk to the closed disk D of
radius 1 centered at 1. Any yn∈ D can be written as y =or exp(ιθ) for θ ∈ [−π/2, π/2] and 0 ≤ r ≤ 2 cos θ.
Qk−1
Consider now the set R ∩
i=1 yi | yi ∈ D for all i for k ≥ 3. We show that this set is exactly the
interval [−τ0 , τ1 ] where τ0 = 2k−1 cosk−1 (π/(k − 1)) and τ1 = 2k−1 . The claim of the lemma then follows
since for the given values of β, 1 − 1/β lies outside [−τ0 , τ1 ] and hence eq. (18) cannot hold.
Recalling that each y ∈ D can be written in the form r exp(ιθ) where θ ∈ [−π/2, π/2] and 0 ≤ r ≤
2 cos θ, we find that the values τ0 and τ1 are defined by the following optimization problems (note that
since k ≥ 3, both programs are feasible):
16

k−1

τ0 = 2

max

k−1
Y

k−1

cos θi

τ1 = 2

i=1

max

k−1
Y

cos θi

i=1

π
π
≤ θi ≤ ,
2
2
k−1
X
θi = π + 2nπ,

π
π
≤ θi ≤ ,
2
2
k−1
X
θi = 2nπ.

subject to −

subject to −

i=1

i=1

for some n ∈ Z

for some n ∈ Z

such that |2n + 1| ≤ (k − 1)/2.

such that |n| ≤ (k − 1)/4.

Using Lemma 4.9, we then see that τ0 = 2k−1 cosk−1 (π/(k − 1)) and τ1 = 2k−1 , as required.



We now proceed to an inductive proof of Theorem 4.4, using Lemma 4.10 as the base case.
Proof of Theorem 4.4. The case k = 2 is a special case of the Lee-Yang theorem [24] (though, as with the
proof of Lemma 4.10, the argument below can again be specialized to directly establish this). We assume
therefore that k ≥ 3.
The proof uses the inductive method of Asano [3]. When the hypergraph consists of a single hyperedge
of size k 0 ≤ k, it follows from Lemma 4.10 and the remark following it that the partition function is LY for
the claimed values of edge activity β. For the induction, we use the fact that the Lee-Yang property of the
partition function is preserved under the following two operations:
(1) Adding a hyperedge: In this operation, a new hyperedge of size k 0 ≤ k and activity β as claimed
in the statement of the theorem, is added to a connected hypergraph in such a way that exactly one
of its k 0 vertices already exists in the starting hypergraph, while the other k 0 − 1 vertices are new.
Note that this operation keeps the hypergraph connected. We assume that the partition functions
of both the original hypergraph as well as the newly added edge separately have the Lee-Yang
property: this follows from the induction hypothesis (for the hypergraph) and Lemma 4.10 (for the
new hyperedge).
(2) Asano contraction: In this operation, two vertices u0 , u00 in a connected hypergraph that are not
both included in any one hyperedge are merged so that the new merged vertex u is incident on
all the hyperedges incident on u0 or u00 in the original graph. Note that this operation keeps the
hypergraph connected and does not change the size of any of the hyperedges.
Any connected non-empty hypergraph G can be constructed by starting with any arbitrary hyperedge
present in G and performing a finite sequence of the above two operations: to add a new hyperedge e with
activity βe as present in G, one first uses operation 1 to add a hyperedge which has the same activity βe
and has new copies of all but one of the incident vertices of e, and then uses operation 2 to merge these new
copies with their counterparts, if any, in the starting hypergraph. Note that in this process, a hyperedge e
can be added only when at least one of its vertices is already included in the current hypergraph. However,
since G is assumed to be connected, its hyperedges can be ordered so that all of them are added by the
above process. Thus, assuming that the above two operations preserve the Lee-Yang property, it follows
by induction on the number of hyperedges that the partition functions of all connected hypergraphs of
hyperedge size at most k, and edge activities βe as claimed in the theorem, have the Lee-Yang property.
The proof of the fact, first proved by Asano [3], that these two operations preserve the Lee-Yang property
are by now standard, and can be found, e.g., in [44, Propositions 1, 2]. We include a proof here for
completeness.
Consider first operation 1. Let G be the original hypergraph and H the new hyperedge (with k 0 ≤ k
vertices) being added, and assume, by renumbering vertices if required, that the vertices being merged
are v1 in G and u1 in H respectively. Let P (z1 , z2 , . . . , zn ) = A(z2 , . . . , zn )z1 + B(z2 , . . . , zn ) and
17

Q(y1 , y2 , . . . , yk0 ) = C(y2 , . . . , yk0 )y1 + D(y2 , . . . , yk0 ) be the Ising partition functions of G and H, respectively, where z1 and y1 are the variables corresponding to v1 and u1 respectively. Both P and Q are LY
by the hypothesis of the operation. The partition function R of the new graph can be written as
R(z, z2 , . . . , zn , y2 , . . . , yk0 ) = A(z2 , . . . , zn )C(y2 , . . . , yk0 )z + B(z2 , . . . , zn )D(y2 , . . . , yk0 ),
where z is a new variable corresponding to the new vertex created by the merger of u and v. Let
λ2 , . . . , λn , µ2 , . . . , µk0 be complex numbers lying outside the open unit disk. In order to prove that R is LY,
we need to show that (i) R(z, λ2 , . . . , λn , µ2 , . . . , µk0 ) = 0 implies that |z| ≤ 1; and (ii) when at least one
of these complex numbers lies strictly outside the closed unit disk then R(z, λ2 , . . . , λn , µ2 , . . . , µk0 ) = 0
implies that |z| < 1. Now, since P and Q are assumed to be LY, Lemma 4.6 implies that A = A(λ2 , . . . , λn )
and C = C(µ2 , . . . , µk0 ) are both non-zero. Thus, R = 0 implies that
(19)

|z| = |B/A| · |D/C| ,

where B = B(λ2 , . . . λn ) and D = D(µ2 , . . . , µk0 ). Since all the λi and µi lie outside the open unit disk
and P and Q are LY, |B/A| , |D/C| ≤ 1, so that from eq. (19) |z| ≤ 1. Further, when at least one of the λi
lies strictly outside the closed unit disk, then again, since P is LY, |B/A| < 1. Similarly,|D/C| < 1 when
one of the µi lies outside the closed unit disk. Thus, when at least one of the λi and the µi lies outside the
closed unit disk, it follows from eq. (19) that |z| < 1. Thus, the conditions (i) and (ii) needed to establish
that R is LY are both satisfied.
We now consider operation 2. By renumbering vertices if necessary, let v1 and v2 be the vertices to be
merged. The partition function P of the original graph (where v1 and v2 are not merged) can be written as
P (z1 , z2 , z3 , . . . , zn ) = A(z3 , . . . , zn )z1 z2 + B(z3 , . . . , zn )z1 + C(z3 , . . . , zn )z2 + D,
and is LY by the hypothesis of the operation. The partition function R after the merger is then given by
R(z, z3 , . . . , zn ) = A(z3 , . . . , zn )z + D,
where z is a new variable corresponding to the new vertex created by the merger of v1 and v2 . Now,
let λ3 , . . . , λn be complex numbers lying outside the open unit disk. Corollary 4.7 then implies that
A = A(λ3 , . . . , λn ) 6= 0. Thus, R(z, λ3 , . . . , λn ) = 0 implies that
(20)

|z| = |D/A| = |D(λ3 , . . . , λn )/A(λ3 , . . . , λn )| .

Now, since P is LY, both zeros of the quadratic equation P (x, x, λ3 , . . . , λn ) = 0 satisfy |x| ≤ 1, and
indeed, |x| < 1 when at least of the λi lies strictly outside the closed unit disk. Thus, the product D/A of
its zeros also satisfies |D/A| ≤ 1, and further satisfies the stronger inequality |D/A| < 1 in case at least
one of the λi lies strictly outside the closed unit disk. Eq. (20) then implies that |z| ≤ 1 in the first case and
|z| < 1 in the second case, which establishes that R is LY.
This concludes the proof of Theorem 4.4.

References
[1] Nima Anari and Shayan Oveis Gharan. The Kadison-Singer problem for strongly Rayleigh measures and applications to
Asymmetric TSP. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), October 2015.
Available at http://arxiv.org/abs/1412.1143.
[2] Nima Anari and Shayan Oveis Gharan. A generalization of permanent inequalities and applications in counting and optimization. arXiv:1702.02937 [cs, math], February 2017.
[3] Taro Asano. Lee-Yang Theorem and the Griffiths Inequality for the Anisotropic Heisenberg Ferromagnet. Physical Review
Letters, 24(25):1409–1411, June 1970.
[4] J. C. A. Barata and D. H. U. Marchetti. Griffiths’ singularities in diluted Ising models on the Cayley tree. J. Stat. Phys.,
88(1-2):231–268, July 1997.
[5] João C. A. Barata and Pedro S. Goldbaum. On the distribution and gap structure of Lee–Yang zeros for the Ising model:
Periodic and aperiodic couplings. J. Stat. Phys., 103(5-6):857–891, June 2001.
[6] Alexander Barvinok. Computing the partition function for cliques in a graph. Theory of Computing, 11(13):339–355, 2015.
18

[7] Alexander Barvinok. Computing the permanent of (some) complex matrices. Found. Comput. Math., 16(2):329–342, January
2015. arXiv:1405:1303.
[8] Alexander Barvinok and Pablo Soberón. Computing the partition function for graph homomorphisms. Combinatorica, May
2016. Available online at http://dx.doi.org/10.1007/s00493-016-3357-2.
[9] Alexander Barvinok and Pablo Soberón. Computing the partition function for graph homomorphisms with multiplicities. J.
Combin. Theory, Ser. A, 137:1–26, January 2016.
[10] Noam Berger, Claire Kenyon, Elchanan Mossel, and Yuval Peres. Glauber dynamics on trees and hyperbolic graphs. Probability
Theory and Related Fields, 131(3):311–340, 2005.
[11] Julius Borcea and Petter Brändén. The Lee-Yang and Pólya-Schur programs. I. Linear operators preserving stability. Invent.
Math., 177(3):541–569, 2009.
[12] Julius Borcea and Petter Brändén. The Lee-Yang and Pólya-Schur programs. II. Theory of stable polynomials and applications.
Comm. Pure Appl. Math., 62(12):1595–1631, 2009.
[13] Julius Borcea, Petter Brändén, and Thomas Liggett. Negative dependence and the geometry of polynomials. J. AMS, 22(2):521–
567, 2009.
[14] Christian Borgs, Jennifer Chayes, Jeff Kahn, and László Lovász. Left and Right Convergence of Graphs with Bounded Degree.
Random Struct. Algorithms, 42(1):1–28, January 2013.
[15] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem. In Automata,
Languages and Programming, volume 6198 of Lecture Notes in Computer Science, pages 275–286. Springer Berlin/Heidelberg,
2010.
[16] Andreas Galanis, Qi Ge, Daniel Štefankovič, Eric Vigoda, and Linji Yang. Improved inapproximability results for counting
independent sets in the hard-core model. Random Struct. Algorithms, 45(1):78–110, 2014.
[17] Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with
mixed signs. SIAM Journal on Computing, 39(7):3336–3402, January 2010.
[18] Leslie Ann Goldberg, Mark Jerrum, and Mike Paterson. The computational complexity of two-state spin systems. Random
Structures & Algorithms, 23(2):133–154, 2003.
[19] Heng Guo and Mark Jerrum. Random cluster dynamics for the Ising model is rapidly mixing. In Proceedings of the Twenty-Eighth
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1818–1827. SIAM, 2017.
[20] Heng Guo and Pinyan Lu. Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems. Approximation,
Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2016.
[21] E. Ising. Beitrag zur Theorie des Ferromagnetismus. Zeitschrift fur Physik, 31:253–258, February 1925.
[22] Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing,
22(5):1087–1116, 1993.
[23] Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform
distribution. Theor. Comput. Sci., 43:169–188, 1986.
[24] T. D. Lee and C. N. Yang. Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model. Phys.
Rev., 87(3):410–419, August 1952.
[25] Liang Li, Pinyan Lu, and Yitong Yin. Correlation decay up to uniqueness in spin systems. In Proc. 24th ACM-SIAM Symp. on
Discrete Algorithms (SODA), pages 67–84. SIAM, 2013.
[26] Yun Long, Asaf Nachmias, Weiyang Ning, and Yuval Peres. A power law of order 1/4 for critical mean-field swendsen-wang
dynamics. Memoirs of the AMS, 232(1092), 2014.
[27] Pinyan Lu, Kuan Yang, and Chihao Zhang. FPTAS for Hardcore and Ising models on hypergraphs. In 33rd Symposium on
Theoretical Aspects of Computer Science, 2016.
[28] Eyal Lubetzky and Allan Sly. Critical ising on the square lattice mixes in polynomial time. Communications in Mathematical
Physics, 313(3):815–836, 2012. Communicated by F. Toninelli.
[29] Adam Marcus, Daniel Spielman, and Nikhil Srivastava. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Ann.
Math., pages 307–325, July 2015.
[30] Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. Interlacing families II: Mixed characteristic polynomials and the
Kadison-Singer problem. Ann. Math., 182:327–350, 2015.
[31] F. Martinelli and E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case.
Comm. Math. Phys., 161(3):447–486, 1994.
[32] F. Martinelli and E. Olivieri. Approach to equilibrium of Glauber dynamics in the one phase region: II. The general case.
Comm. Math. Phys., 161:487–514, 1994.
[33] Fabio Martinelli, Alistair Sinclair, and Dror Weitz. Glauber dynamics on trees: Boundary conditions and mixing time.
Communications in Mathematical Physics, 250(2):301–334, 2004.
[34] Elchanan Mossel and Allan Sly. Exact thresholds for Ising-Gibbs samplers on general graphs. Ann. Probab., 41(1):294–328,
2013.
[35] Viresh Patel and Guus Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph
polynomials. arXiv:1607.01167 [cs, math], July 2016. arXiv: 1607.01167.
19

[36] Dana Randall and David Wilson. Sampling spin configurations of an Ising system. In Proc. 10th ACM-SIAM Symp. Discret.
Algorithms (SODA), SODA ’99, pages 959–960, Philadelphia, PA, USA, 1999. SIAM.
[37] David Ruelle. Characterization of Lee-Yang polynomials. Ann. Math., 171(1):589–603, March 2010.
[38] Alex Scott and Alan Sokal. The Repulsive Lattice Gas, the Independent-Set Polynomial, and the Lovász Local Lemma. J. Stat.
Phys., 118(5-6):1151–1261, 2004.
[39] James B. Shearer. On a problem of Spencer. Combinatorica, 5(3), 1985.
[40] Alistair Sinclair and Piyush Srivastava. Lee-Yang theorems and the complexity of computing averages. Comm. Math. Phys.,
329(3):827–858, August 2014.
[41] Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin
systems on bounded degree graphs. J. Stat. Phys., 155(4):666–686, 2014.
[42] Allan Sly and Nike Sun. Counting in two-spin models on d-regular graphs. Ann. Probab., 42(6):2383–2416, November 2014.
[43] R.P. Stanley and S. Fomin. Enumerative Combinatorics:. Number v. 2 in Cambridge Studies in Advanced Mathematics.
Cambridge University Press, 1999.
[44] Masuo Suzuki and Michael E. Fisher. Zeros of the partition function for the Heisenberg, Ferroelectric, and general Ising
models. J. Math. Phys., 12(2):235–246, 1971.
[45] Dror Weitz. Counting independent sets up to the tree threshold. In Proc. 38th ACM Symp. on Theory of Computing (STOC),
pages 140–149. ACM, 2006.
[46] C. N. Yang and T. D. Lee. Statistical theory of equations of state and phase transitions. I. Theory of condensation. Phys. Rev.,
87(3):404–409, August 1952.
[47] Jinshan Zhang, Heng Liang, and Fengshan Bai. Approximating partition functions of the two-state spin system. Inf. Process.
Lett., 111(14):702–710, July 2011.

20

