On a conjecture of Sokal concerning roots of the independence polynomial
Han Peters Guus Regts

Modelling Competitive Sports:

Bradley-Terry-Élő Models
 for Supervised and On-Line Learning
 of Paired Competition Outcomes
    [
    January 27, 2017
============================================================================================================================

A conjecture of Sokal <cit.> regarding the domain of non-vanishing for independence polynomials of graphs, states that given any natural number Δ≥ 3, there exists a neighborhood in ℂ of the interval [0, (Δ-1)^Δ-1/(Δ-2)^Δ) on which the independence polynomial of any graph with maximum degree at most Δ does not vanish. We show here that Sokal's Conjecture holds, as well as a multivariate version, and prove optimality for the domain of non-vanishing. An important step is to translate the setting to the language of complex dynamical systems.


Keywords: Independence polynomial, hardcore model, complex dynamics, roots, approximation algorithms.





§ INTRODUCTION

For a graph G=(V,E) and λ=(λ_v)_v∈ V∈^V, the multivariate independence polynomial, is defined as

    Z_G(λ):=∑_I⊆ V
    independent∏_v∈ Iλ_v.

We recall that a set I⊆ V is called independent if it does not span any edges of G.
The univariate independence polynomial, which we also denote by Z_G(λ), is obtained from the multivariate independence polynomial by plugging in λ_v=λ for all v∈ V.

In statistical physics the univariate independence polynomial is known as the partition function of the hardcore model. When λ=1, Z_G(λ) equals the number of independent sets in the graph G.

Motivated by applications in statistical physics Sokal <cit.> asked about domains of the complex plane where the independence polynomial does not vanish.
Just below Question 2.4 in <cit.>, Sokal conjectures: “there is a complex domain D_Δ containing at least the interval 0≤λ<1/(Δ-1) of the real axis — and possibly even the interval 0≤λ<λ_Δ:=(Δ-1)^Δ-1/(Δ-2)^Δ — on which Z_G(λ) does not vanish for all graphs of maximum degree at most Δ".

In this paper we confirm the strong form of his conjecture for the univariate independence polynomial.
In Section <ref> we will prove the following result:

Let Δ∈ℕ with Δ≥ 3. Then there exists a complex domain D_Δ containing the interval 0≤λ<λ_Δ such that for any graph G=(V,E) of maximum degree at most Δ and any λ∈ D_Δ, we have that Z_G( λ)≠ 0.

If we allow ourselves an epsilon bit of room, then the same result also holds for multivariate independence polynomial. This is the contents of Theorem <ref> in Section <ref>. We show in Appendix <ref> that the literal statement of Theorem <ref> does not hold in the multivariate setting.

It follows from nontrivial results in complex dynamical systems that the bound in Theorem <ref> is in fact optimal, in light of the following:

Let Δ∈ℕ with Δ≥ 3. Then there exist λ∈ℂ arbitrarily close to λ_Δ for which there exists a graph G of maximum degree Δ with Z_G(λ)=0.

This result is a direct consequence of Proposition <ref> in Subsection <ref>.
We discuss the underlying results from the theory of complex dynamical systems in Appendix <ref>.

Other results for the nonvanishing of the independence polynomial include a result of Shearer <cit.> that says that for any graph G=(V,E) of maximum degree at most Δ and any λ such that for each v∈ V, |λ_v|≤(Δ-1)^Δ-1/Δ^Δ one has Z_G(λ)≠ 0. See <cit.> for a slight improvement and extensions.
Moreover, Chudnovsky and Seymour <cit.> proved that the univariate independence polynomial of a claw-free graph (a graph G is called claw-free if it does not contain four vertices that induce a tree with three leaves), has all its roots on the negative real axis.



  §.§.§ Motivation

Another motivation for Theorem <ref> comes from the design of efficient approximation algorithms for (combinatorial) partition functions.
In <cit.> Weitz showed that there is a (deterministic) fully polynomial time approximation algorithm (FPTAS) for computing Z_G(λ) for any 0≤λ<λ_c(Δ) for any graph of maximum degree at most Δ. His method is often called the correlation decay method and has subsequently been used and modified to design many other FPTAS's for several other types of partition functions; see e.g. <cit.>.
More recently, Barvinok initiated a line of research that led to quasi-polynomial time approximation algorithms for several types of partition functions and graph polynomials; see e.g. <cit.> and Barvinok's recent book <cit.>.
This approach is based on Taylor approximations of the log of the partition function/graph polynomial, and allows to give good approximations in regions of the complex plane where the partition function/polynomial does not vanish.
In his recent book <cit.>, Barvinok refers to this approach as the interpolation method.
Patel and the second author <cit.> recently showed that the interpolation method in fact yields polynomial time approximation algorithms for these partition functions/graph polynomials when restricted to bounded degree graphs.

In combination with the results in Section 4.2 from <cit.>, Theorem <ref> immediately implies that the interpolation methods yields a polynomial time approximation algorithm for computing the independence polynomial at any fixed 0≤λ<λ_Δ on graphs of maximum degree at most Δ, thereby matching Weitz's result.
In particular, Theorem <ref> gives evidence for the usefulness of the interpolation method.



 §.§ Preliminaries

We collect some preliminaries and notational conventions here.
Graphs may be assumed to be simple, as vertices with loops attached to them can be removed from the graph and parallel edges can be replaced by single edges without affecting the independence polynomial.
Let G=(V,E) be a graph. For a subset U⊆ V we denote the graph induced by U by G[U].
For U⊂ V we denote the graph induced by V∖ U by G∖ U; in case U={u} we just write G-u.
For a vertex v∈ V we denote by N[v]:={u∈ V|{u,v}∈ E}∪{v} the closed neighborhood of v.
The maximum degree of G is the maximum number of neighbors of a vertex over all vertices of G. This is denoted by Δ(G).

For Δ∈ and k∈ we denote by T_Δ,k the rooted tree, recursively defined as follows: for k=0, T_Δ,0 consists of a single vertex; for k>0, T_Δ,k consists of the root vertex, which is connected to the Δ-1 root vertices of Δ-1 disjoint copies of T_Δ,k-1.
We will sometimes, abusing terminology, refer to the T_Δ,k as regular trees.
Note that the maximum degree of T_Δ,k equals Δ whenever k≥ 2 and equals Δ-1 when k=1.



Organization
The remainder of this paper is organised as follows. In the next section we translate the setting to the language of complex dynamical systems and we prove another non-vanishing result for the multivariate independence polynomial, cf. Theorem <ref>.
Section <ref> contains technical, yet elementary, derivations needed for the proof of our main result, which is given in Section <ref>. We conclude with some questions in Section <ref>.
In the appendix we discuss results from complex dynamical systems theory needed to prove Proposition <ref>.





§ SETUP

We will introduce our setup in this section.


Let us fix a graph G=(V,E), λ=(λ_v)_v∈ V∈^V and a vertex v_0∈ V.
The fundamental recurrence relation for the independence polynomial is

    Z_G(λ)=λ_v_0 Z_G∖ N[v_0](λ)+Z_G-v_0(λ).

Let us define, assuming Z_G-v_0(λ)≠ 0,

    R_G,v_0=λ_v_0 Z_G∖ N[v_0](λ)/Z_G-v_0(λ).

In the case that λ_v>0 for all v∈ V (<ref>) is always defined.
This definition is inspired by Weitz <cit.>.
We note that by (<ref>),

    R_G,v_0≠ -1  if and only if  Z_G(λ)≠ 0.

So for our purposes it suffices to look at the ratio R_G,v_0.



 §.§ Regular trees

We now consider the univariate independence polynomial for the trees T_Δ,k.
Let v_k denote the root vertex of T_Δ,k.
Then for k>0, T_Δ,k-v_k is equal to the disjoint union of Δ-1 copies of T_Δ,k-1.
Additionally, for k>1, T_Δ,k∖ N[v_k] is equal to the disjoint union of Δ-1 copies of T_Δ,k-1-v_k-1.
Using this we note that for k>2 (<ref>) takes the following form:

    R_T_Δ,k,v_k   =λ(Z_T_Δ,k-1-v_k-1/Z_T_Δ,k-1)^Δ-1
    =λ(Z_T_Δ,k-1-v_k-1/λ Z_T_Δ,k-1∖ N[v_k-1]+Z_T_Δ,k-1-v_k-1)^Δ-1
       =λ/(1+R_T_Δ,k-1,v_k-1)^Δ-1.


We denote the extended complex plane ∪{∞} by .
Define for λ∈ and d∈, f_d,λ:→ by

    f_d,λ(x)=λ/(1+x)^d.

So (<ref>)  gives that R_T_Δ,k,v_k=f_Δ-1,λ(R_T_Δ,k-1,v_k-1).
Noting that R_T_Δ,v_0=λ, we observe that R_T_Δ,k,v_0=f_Δ-1,λ^∘ k(λ).
So to understand under which conditions R_T_Δ,k,v_k equals -1 or not, it suffices to look at the orbits of f_Δ-1,λ with starting point λ, or equivalently with starting point -1.


A somewhat similar relation between graphs and the iteration of rational maps was explored by Bleher, Roeder and Lyubich in <cit.> and <cit.>. While here one iteration of f_Δ-1,λ corresponds to adding an additional level to a tree, there one iteration corresponded to adding an additional refinement to a hierarchical lattice.

Let us denote by U_d⊂ the open set of parameters λ for which f_d,λ has an attracting fixed point.
Then

    U_d={-α d^d/(d+α)^d+1| |α|<1}.

Indeed, writing f=f_d,λ, we note that if x is a fixed point of f we have

    f^'(x)=-d/1+xλ/(1+x)^d=-dx/1+x.

Let α∈.
Then f^'(x)=α if and only if x=-α/d+α and consequently,

    λ=x(1+x)^d=-α d^d/(d+α)^d+1.

A fixed point x = f(x) is attracting if and only if |f^'(x)|<1, which implies the description (<ref>). For parameters λ in the boundary ∂ U_Δ-1 the function f has a neutral fixed point, and for a dense set of parameters λ∈∂ U_Δ - 1 the fixed point is parabolic, i.e. the derivative at the fixed point is a root of unity. Classical results from complex dynamical systems allow us to deduce the following regarding the vanishing/non-vanishing of the independence polynomial:

Let Δ∈ be such that Δ≥ 3. Then


  (i) for all k∈ and λ∈ U_Δ-1, Z_T_Δ,k(λ)≠ 0;

  (ii) if λ∈∂ U_Δ-1, then for any open neighborhood U of λ there exists λ'∈ U and k∈ such that Z_T_Δ,k(λ')=0.


We note that for λ=-(Δ-1)^Δ-1/Δ^Δ part (ii) was proved by Shearer <cit.>; see also <cit.>.
Part (i) follows quickly from elementary results in complex dynamics, but the statements that imply part (ii) are less trivial. The necessary background from the complex dynamical systems, including the proof of Proposition <ref> and a counterexample to the multivariate statement of Theorem <ref>, will be discussed in Appendix <ref>. Note that Proposition <ref> from the introduction is a special case of Proposition <ref>.

So we can conclude that Sokal's conjecture is already proved for regular trees.
We now move to general (bounded degree) graphs.



 §.§ A recursive procedure for ratios for all graphs

It will be convenient to have an expression similar to (<ref>) for all graphs.
Let G be a graph with fixed vertex v_0.
Let v_1,…,v_d be the neighbors of v_0 in G (in any order). Set G_0=G-v_0 and define for i=1,…,d, G_i:=G_i-1-v_i.
Then G_d=G∖ N[v_0].
The following lemma gives recursive relation for the ratios and has been used before over the real numbers in e.g. <cit.>.

Suppose Z_G_i(λ)≠ 0 for all i=0,…,d.
Then

    R_G,v_0=λ_v_0/∏_i=1^d (1+R_G_i-1,v_i).



Let us write

    Z_G-v_0(λ)/Z_G∖ N[v_0](λ)   =Z_G_0(λ)/Z_G_1(λ)Z_G_1(λ)/Z_G_2(λ)⋯Z_G_d-1(λ)/Z_G_d(λ)=∏_i=1^dZ_G_i(λ)+λ_v_iZ_G_i-1∖ N[v_i]/Z_G_i(λ)
       =∏_i=1^d(1+R_G_i-1,v_i),

where in the second equality we use (<ref>).
As

    R_G,v_0=λ_v_0 Z_G∖ N[v_0](λ)/Z_G-v_0(λ)=λ_v_0/Z_G-v_0(λ)/Z_G∖ N[v_0](λ),

the lemma follows.


As an illustration of Lemma <ref> we will now prove a result that shows that Z_G(λ) is nonzero as long as the norms and arguments of the λ_v are small enough. This result is implied by our main theorem for angles that are much smaller still, but the statement below is not implied by our main theorem, and is another contribution to Sokal's question <cit.>.
The proof moreover serves as warm up for the proof of our main result.


Let G=(V,E) be any graph of maximum degree at most Δ≥ 2.
Let >0 and let λ∈^V be such that |λ_v|≤tan(π/(2+)(Δ-1)), and such that |(λ_v)|</2/2+π for all v∈ V. Then Z_G(λ)≠ 0.





Since the independence polynomial is multiplicative over the disjoint union of graphs, we may assume that G is connected.
Fix a vertex v_0 of G.
We will show by induction that for each subset U⊆ V∖{v_0} we have


  (i) Z_G[U](λ)≠ 0,

  (ii)if u∈ U has a neighbor in V∖ U, then |R_G[U],u|<tan(π/(2+)(Δ-1)),

  (iii)if u∈ U has a neighbor in V∖ U, then (R_G[U],u)>0.

Clearly, if U=∅ both (i), (ii) and (iii) are true.
Now suppose U⊆ V∖{v_0} and let H=G[U].
Let u_0∈ U be such that u_0 has a neighbor in V∖ U (u_0 exists as G is connected).
Let u_1,…,u_d be the neighbors of u_0 in H. Note that d≤Δ-1.
Define H_0=H-u_0 and set for i=1,…,d H_i=H_i-1-u_i.
Then by induction we know that for i=0,…,d, Z_H_i(λ)≠ 0 and for i≥ 1, (R_H_i-1,u_i)>0, implying that |1+R_H_i-1,u_i|≥ 1.
So by Lemma <ref> we know that

    |R_H,u_0|=|λ_u_0|/∏_i=1^d |1+R_H_i-1,u_i|<|λ_u_0|≤tan(π/(2+)(Δ-1)),

showing that (ii) holds for U.

To see that (iii) holds we look at the angle α that R_H,u_0 makes with the positive real axis.
It suffices to show that |α|<π/2.
Since by induction (R_H_i-1,u_i)>0 and  |R_H_i-1,u_i|≤tan(π/(2+)(Δ-1)), we see that the angle α_i that 1+R_H_i-1,u_i makes with the positive real axis satisfies |α_i|≤π/(2+)(Δ-1).
This implies by Lemma <ref> that

    |α|<(Δ-1)π/(2+)(Δ-1)+(/2)π/2+= π/2,

showing that (iii) holds.

As by (iii), R_H,u_0 has strictly positive real part and hence does not equal -1 we conclude by (<ref>) that Z_H(λ)≠ 0.
So we conclude that (i), (ii) and (iii) hold for all U⊆ V∖{v_0}.

To conclude the proof, it remains to show that Z_G(λ)≠ 0.
Let v_1,…,v_d be the neighbors of v_0. Let G_i, for i=0,…,d, be defined as the graphs H_i above.
Then by (i) and (ii) we know that for i=0,…,d, Z_G_i(λ)≠ 0 and (R_G_i-1,v_i)>0 for i≥ 1.
So as above we have



that the angle α_i, that 1+R_G_i-1,v_i makes with the positive real line, satisfies |α_i|≤π/(2+)Δ-1.
So by Lemma <ref> the absolute value of the argument of R_G,v_0 is bounded by

    (/2)π/2++Δπ/(2+)(Δ-1)≤(2+/2)π/2+<π,

using that Δ/Δ-1≤ 2.
This implies by (<ref>) that Z_G(λ)≠0 and finishes the proof.


Define for λ∈ and d∈ the map F_d,λ:^d→ by

    (x_1,…,x_d)↦λ/∏_i=1^d(1+x_i).

Given ϵ>0, the proof of Theorem <ref> consisted mainly of finding a domain D⊂ not containing -1 such that if x_1, … ,x_d ∈ D, then F_d,λ(x_1, …, x_d) ∈ D for all 0 ≤ d ≤Δ-1.

To prove Theorem <ref>, we will similarly construct for each Δ a domain D, containing the interval [0, λ_Δ] but not the point -1, which is mapped inside itself by f_d,λ for all 0≤ d≤Δ-1 and all λ in a sufficiently small complex neighborhood of the interval [0,(1-ϵ)λ_Δ). Had these functions f_d,λ all been strict contractions on the interval [0, λ_Δ], the existence of such a domain D would have been immediate. Unfortunately the functions f_d,λ are typically not contractions, even for real valued λ. However, since the positive real line is contained in the basin of an attracting fixed point, it follows from basic theory of complex dynamical systems <cit.> that each f_d,λ is strictly contracting on [0,λ_Δ) with respect to the Poincaré metric of the corresponding attracting basin. While these Poincaré metrics vary with λ and d, this observation does give hope for finding coordinates with respect to which all the maps f_d,λ are contractions.


In the next section we will introduce explicit coordinates with respect to which f_Δ-1,λ_Δ becomes a contraction, and then show that for d ≤Δ-1 and λ∈ [0, λ_Δ) the maps f_d, λ are all strict contractions with  respect to the same coordinates. We will then utilize these coordinates to give a proof of Theorem <ref> in Section <ref>.



§ A CHANGE OF COORDINATES


It is our aim in this section to find a coordinate change for each Δ≥ 3 so that the maps f_d,λ are contractions in these coordinates for any 0≤ d≤Δ-1 and any 0≤λ≤λ_Δ.



 §.§ The case d=Δ-1 and λ=λ_Δ

We consider the coordinate changes.

    z = φ_y(x) = log(1+ylog(1+x)),

with y>0. We note that a similar coordinate change using a double logarithm was used in <cit.>. The best argument for using the specific form above is that it seems to fit our purposes.

Our initial goal is to pick a y, depending on Δ such that the parabolic map f(x):=f_Δ-1,λ_Δ(x) becomes a contraction with respect to the new coordinates. Note that we call f parabolic if λ = λ_Δ.
In this case the fixed point of f is given by

    x_Δ=1/Δ-2 = 1/d-1,

and has derivative f^'(x_Δ) = -1, and is thus parabolic.
In the z-coordinates we consider the map

    g(z) = g_Δ-1,λ_Δ(z) = φ_y ∘ f  ∘φ_y^-1.

Note that the function φ_y:ℝ_+ →ℝ_+ is bijective, and ℝ_+ is forward invariant under f. It follows that the composition g is well defined on ℝ_+.
We write z_Δ:= φ_y(x_Δ).
Then z_Δ is fixed under g, and one immediately obtains g^'(z_Δ) = -1. Thus, in order for |g^'| ≤ 1 we in particular need that g^''(z_Δ) = 0.

Let us start by computing g^' and g^''.
Writing x_1 = f(x_0) and z_0 = φ_y(x_0) we note that

    g^'(z_0) =    φ_y^'(x_1) · f^'(x_0) · (φ_y^-1)^'(z_0) 
    
    =    φ_y^'(x_1)/φ_y^'(x_0)· f^'(x_0)	
    
    =    1+ ylog(1+x_0)/1+ylog(1+x_1)·1+x_0/1+x_1·-d x_1/1+x_0
    
    =    1+ ylog(1+x_0)/1+ylog(1+x_1)·-d x_1/1+x_1.

Now note that

    g^'' = ∂ g^'/∂ x_0·∂ x_0/∂ z_0,

and since ∂ x_0/∂ z_0 > 0, we look for points z_0 where ∂ g^'/∂ x_0(z_0) = 0. We obtain

    ∂ g^'/∂ x_0(z_0)  =    y/(1+x_0)/1+ylog(1+x_1)·-d x_1/1+x_1
    
     +     (1+ ylog(1+x_0)) ·∂/∂ x_1( 1/1+ylog(1+x_1)·-d x_1/1+x_1) ·∂ x_1/∂ x_0.

By considering x_1 as a variable depending on x_0, and thus also on z_0, the presentation of the calculations here and later in this section becomes significantly more succinct. Since

    ∂ x_1/∂ x_0=-dx_1/1+x_0,

and since

    ∂/∂ x_1( 1/1+ylog(1+x_1)·-dx_1/1+x_1) = d ·x_1 y - (1+ylog(1+x_1))/(1+x_1)^2(1+ylog(1+x_1))^2,

we obtain

    ∂ g^'/∂ x_0(z_0)  =   y/(1+x_0)/1+ylog(1+x_1)·-d x_1/1+x_1
       +(1+ ylog(1+x_0))-d^2x_1/1+x_0·x_1 y - (1+ylog(1+x_1))/(1+x_1)^2(1+ylog(1+x_1))^2.



The only value of y > 0 for which g^''(z_Δ) = 0 is given by

    y = y_Δ := 1/2x_Δ - log(1+x_Δ).



Noting that x_1 = x_0 and dx_1/(1+x_1)=1 when x_0 = x_Δ, we obtain

    ∂ g^'/∂ x_0(z_Δ) = d ·1+ylog(1+x_Δ) - 2x_Δ y/(1+ylog(1+x_Δ))(1+x_Δ)^2.

Thus g^''(z_Δ) = 0 if and only if

    y=y_Δ := 1/2x_Δ - log(1+x_Δ).



From now on we assume that y = y_Δ.


We have that |g^'(z)| ≤ 1 for all z ≥ 0.


Since

    lim_z → +∞ |g^'(z)| = 0,

it suffices to show that |g^'(0)| < 1, which follows if we show that g^''(0)<0, for which it is sufficient to show that ∂ g^'/∂ x_0(0)<0.

Plugging in x_0=0 in (<ref>) we get

    ∂ g^'/∂ x_0(0) = dx_1(d - y(1+x_1))(1+ylog(1+x_1) - dx_1 y)/(1+ylog(1+x_1))^2(1+x_1)^2,

with x_1 = f(0) = λ. Hence we can complete the proof by showing that

    d - y(1+λ) = d - y - yλ < 0.

Using that 1/y=2/(d-1)-log(d/(d-1)) we observe that

    1/y<1/d-1+1/2(d-1)^2

and hence y > (d-1)^2/d-1/2 .
From this we obtain

    d - y - yλ   <d(d-1/2)-(d-1)^2-(d-1)(d/(d-1))^d)/d-1/2
       <d(d-1/2)-(d-1)^2-(d-1)(1+d/(d-1))/d-1/2=-d/2/d-1/2<0,

which completes the proof.


In particular it follows that for all x ≥ 0 we have that f^∘ n(x) → x_Δ.



 §.§ Smaller values of λ and d

We now consider the case where λ < λ_Δ, and the map f has degree d≤Δ-1.
We again consider the map

    g_d,λ(z)=φ_y∘ f_d,λ∘φ^-1_y.

Again we will often just write g instead of g_d,λ.
Our goal is to show that |g^'(z_0)| < 1 for all z_0 ≥ 0.

To do so we will consider g^' as a function of λ,d and z_0.
We first look at the case where λ is fixed and d is varying.


Let Δ∈ with Δ≥ 3.
Let 0≤λ≤λ_Δ and let d∈{0,1,…,Δ-1}.
Let z_0≥ 0 be such that g^''_d,λ(z_0)=0. Then we have 0≥ g_d,λ^'(z_0)≥ g_Δ-1,λ^'(z_0).


We will consider the derivative of g^' with respect to d in the points z_0 where g^''(z_0)=0.
By (<ref>), g^''(z_0) is a multiple of

    y/1+ylog(1+x_1)·1/1+x_1 + -d (1+ylog(1+x_0)) ·1+ylog(1+x_1)-x_1y/(1+x_1)^2(1+ylog(1+x_1))^2.

As g^''(z_0) =0, we obtain

    y(1+x_1)(1+ylog(1+x_1)) = d (1+ylog(1+x_0)) · (1+ylog(1+x_1) - x_1 y).

In particular we get that

    1 + y log(1+x_1) - x_1 y > 0,

and

    dlog(1+x_0) = (1+x_1)(1+ylog(1+x_1))/1+ylog(1+x_1)-x_1y - d/y.

Now notice that by (<ref>) we have that ∂/∂ d g^' is a positive multiple of

    -x_1/(1+x_1)(1+ylog(1+x_1)+∂ x_1/∂ d·∂/∂ x_1( 1/1+ylog(1+x_1)·-dx_1/1+x_1),

which by (<ref>) is a positive multiple of

    - (1+x_1) (1 + y log(1+x_1)) + dlog(1+x_0) · (1 + y log(1+x_1) - x_1 y).

When we plug in equation (<ref>) to eliminate x_0 from this expression, we note that the term (1+x_1)(1+ylog(1+x_1)) cancels and we obtain that ∂/∂ dg^' is a positive multiple of

    - d/y(1 + ylog(1+x_1) - x_1 y),

which is negative as observed in (<ref>).

So, we see that as we decrease d the value of g^'(z_0) increases and hence it follows that 0≥ g_d,λ^'(z_0) ≥  g_Δ-1,λ^'(z_0), as desired.


We next compute the derivative of g^' with respect to λ.
Note that x_1 depends  on λ, but x_0 does not, hence

    ∂ g^'/∂λ (z_0) = (1+ y log(1+x_0)) ·∂/∂λ(-dx_1/(1+x_1)(1+ylog(1+x_1)))
    
    = (1+ y log(1+x_0)) ·∂ x_1/∂λ·∂/∂ x_1(-dx_1/(1+x_1)(1+ylog(1+x_1))) .

Thus ∂ g^'/∂λ (z_0) = 0 if and only if

    ∂/∂ x_1(-dx_1/(1+x_1)(1+ylog(1+x_1))) = 0,

which, by (<ref>) is the case if and only if

    x_1 y - (1+ylog(1+x_1)) = 0.



Let Δ≥ 5. For any λ≤λ_Δ and 0≤ d≤Δ-1, we have

    x_1 y - (1+ylog(1+x_1))<0.

In particular g^'(z_0) is decreasing in λ for any z_0≥ 0.


We note that x_1 y - (1+ylog(1+x_1)) is increasing in x_1 for x_1>0.
So it suffices to plug in λ=λ_Δ and x_0=0, that is, plug in x_1=λ_Δ.
Note that this makes it independent of d.

Plugging in x_1=λ_Δ we get

    λ_Δ y-(1+ylog(1+λ_Δ)=y(λ_Δ-(1/y+log(1+λ_Δ)),

So as y>0 is suffices to show

    c(Δ):=λ_Δ-(1/y+log(1+λ_Δ)<0.

By a direct computer calculation, we obtain the following approximate values for c(Δ) for Δ∈{5,6,7}:

    [       Δ       5       6       7;    c(Δ) -0.0450 -0.0809 -0.0887;         ]

and we conclude that (<ref>) holds for Δ∈{5,6,7}.

Using that x-x^2/2≤log(1+x)≤ x for all x≥ 0, we obtain

    λ_Δ-(1/y+log(1+λ_Δ)≤   λ_Δ-(x_Δ +λ_Δ-λ_Δ^2/2)
    
    
    =   λ_Δ^2/2-1/Δ-2.

Using that

    λ_Δ=Δ-1/(Δ-2)^2(Δ-1/Δ-2)^Δ-2≤e(Δ-1)/(Δ-2)^2,

we obtain that

    λ_Δ-(1/y+log(1+λ_Δ))≤e^2(1+1/Δ-2)^2-2(Δ-2)/2(Δ-2)^2.

Since the right-hand side of (<ref>) is negative for Δ=8 and since the numerator is clearly decreasing in Δ, we conclude that (<ref>) is true for all Δ≥ 8. This concludes the proof.




 
Let Δ∈{3,4}.
Let z_0>0 and λ_0>0 be such that

    ∂/∂λg^'_Δ-1,λ(z_0) = 0

for λ = λ_0. Then g^'_Δ-1,λ_0(z_0)≥ -0.92.


By assumption we have ∂ g^'(z_0)/∂λ = 0. Thus (<ref>) implies that

    x_1 y = 1 + y log(1 + x_1),

This implies that for x_1 to be a solution to (<ref>), we need that x_1≥ x_Δ.
Indeed suppose that x_1<x_Δ. Then we have from (<ref>) that

    x_1y=1+ylog(1+x_1)>1+yx_1-yx_1^2/2,

from which we obtain yx_1^2>2.
However, as y<1/x_Δ we have yx_1^2<yx_Δ^2<x_Δ<2, a contradiction.

Now (<ref>) combined with (<ref>) gives

    g^'(z_0)=1+ylog(1+x_0)/yx_1·-(Δ-1)x_1/1+x_1 = -(Δ-1)(1+ylog(1+x_0))/y(1+x_1).


Now recall that y=y_Δ satisfies

    2x_Δ y = 1+ylog(1+x_Δ)  .

Now using that x_1≥ x_Δ and by combining (<ref>) and (<ref>) we obtain

    x_1=1+ylog(1+x_1)/y=2x_Δ(1+ylog(1+x_1)/1+ylog(1+x_Δ))≥ 2x_Δ.

Using this we obtain

    x_1=   2x_Δ(1+ylog(1+x_1)/1+ylog(1+x_Δ))≥ 2x_Δ(1+ylog(1+2x_Δ)/1+ylog(1+x_Δ))
    
    
    =   2x_Δ( 1+log(1+2x_Δ)/2x_Δ-log(1+x_Δ)/1+log(1+x_Δ)/2x_Δ-log(1+x_Δ))=2x_Δ+log(1+2x_Δ/1+x_Δ)=α_Δ x_Δ,

where α_3=2+log(3/2)≈ 2.405, and where α_4=2+2log(4/3))≈ 2.575.
This then implies that

    1+x_0≤ (λ_Δ/x_1)^1/(Δ-1)≤α_Δ^-1/(Δ-1)(1+x_Δ).

Since (<ref>) is decreasing in x_0 and increasing in x_1, we can plug in x_0=α_Δ^-1/(Δ-1)(1+x_Δ) and x_1=α_Δ x_Δ to obtain

    g_Δ-1,λ_0^'(z_0) >    -(Δ-1)(1+ylog(α_Δ^-1/(Δ-1)(1+x_Δ))/y(1+α_Δ x_Δ)
    =
    -2(Δ-1)x_Δ y + ylog (α_Δ)/y(1+α_Δ x_Δ)
    
     =    -2(Δ-1)/(Δ-2) + log(α_Δ)/(Δ-2+α_Δ)/(Δ-2)≈{[ -0.9168 if Δ=3,; -0.8979 if Δ=4. ].

This finishes the proof.



We can now finally show that the coordinate changes works for all values of the parameters we are interested in.

 
Let Δ≥ 3 and let >0. Then there exists δ>0 such that if 0≤λ<(1-)λ_Δ, then |g^'_d,λ(z_0)|<1-δ for all z_0≥ 0 and d∈{0,1,…,Δ-1}.




Let J=[0,(1-)λ_Δ] and let

    M:=min_z_0≥ 0,λ∈ J,d=0,…, Δ-1 g^'_d,λ(z_0).

As for any λ∈ J we have that lim_z_0→∞g^'_d,λ(z_0)=0 and as g^''(0)<0 by the proof of Corollary <ref> (which remains valid as (<ref>) is decreasing in d) it follows that we may assume that M is attained at some triple (z_0,λ_0,d) with z_0>0, λ_0∈ J and d∈{0,…,Δ-1}.
This then implies that g_d,λ_0^''(z_0)=0 and hence by Lemma <ref> we know that g^'_d,λ_0(z_0)≥ g^'_Δ-1,λ_0(z_0),
that is, we have that d=Δ-1.

If g^'_d,λ_0(z_0) attains its minimum (as a function of λ) at some λ<λ_Δ, then ∂/∂λ g^'(z_0)=0. So by Lemma <ref> we know that Δ∈{3,4}.
Then Lemma <ref> implies that  M≥ -0.92.
So we may assume that g^' is strictly decreasing as a function of λ on [0,λ_Δ].
This then implies that λ_0=(1-)λ_Δ and so there exists δ>0 (and we may assume δ<0.08)
such that

    M=g_d,λ_0^'(z_0)> (1-δ) g_d,λ_Δ^'(z_0)≥ -1+δ,

where the last inequality is by Corollary <ref>.
This finishes the proof.








§ PROOF OF THEOREM <REF>


Our proof will essentially follow the same pattern as the proof of Theorem <ref>, but instead of working with the function F_d,λ we now need to work with a conjugation of F_d,λ.
Let Δ≥ 3.
Recall from the previous section the function φ:_+→_+ defined by z = φ(x) = log(1+ylog(1+x)), with y=y_Δ.
We now extend the function φ to a neighborhood V ⊂ of _+ by taking the branch for both logarithms that is real for x >0. By making V sufficiently small we can guarantee that φ is invertible. Now define for d=0,…, Δ-1, the map G_d,λ: φ(V)^d → by

    (z_1,…,z_d)↦φ(λ/∏_i=1^d 1+φ^-1(z_i)).

For a set A⊂ and >0 we write 𝒩(A,):={z∈| |z-a|< for some a∈ A}.
Now define for >0 the set D()⊂ by

    D():=𝒩([0,φ(λ_Δ)],).

We collect a very useful property:

Let Δ≥ 3 and let >0.
Then there exist _1,_2>0 such that for any λ∈Λ(_2):=

𝒩([0,(1-)λ_Δ ],_2), any d=0,…,Δ-1 and z_1,…,z_d∈ D(_1) we have G_d,λ(z_1,…,z_d)∈ D(_1).


We first prove this for the special case that z_1=z_2=…=z_d=z.
In this case we have G_d,λ(z_1,…,z_d)=g_d,λ(z).
By Proposition <ref> we know that there exists δ>0 such that for any d=0,…,Δ-1 we have

    |g^'_d,λ(z)|<1-δ for all λ∈ [0,(1-)λ_Δ]  and  z∈ [0,φ(λ_Δ)].

By continuity of g^' as a function of z and λ there exists _1,_2>0 such that for all d=0,…,Δ-1 and each (z,λ)∈ D(_1)×Λ(_2)

we have

    |g_d,λ^'(z)|≤ 1-δ/2.

We may assume that _2 is small enough so that for any d,

    sup_λ∈Λ(_2),z∈ [-_1,φ (λ_Δ)]|∂/∂λg_d,λ(z)|≤δ_1/2_2,


Fix now λ∈Λ(_2) and d and let z∈ D(_1).
Let z'∈ [0,φ(λ_Δ)] be such that |z-z'|< _1 and let λ'∈ [0,(1-)λ_Δ)) be such that |λ-λ'|<_2
Then

    |g_d,λ(z)-g_d,λ'(z')|≤   |g_d,λ(z)-g_d,λ(z')|+|g_d,λ(z')-g_d,λ'(z')|
    
    
    <     (1-δ/2)_1+_1δ/2<_1,

implying that the distance of g_d,λ(z) to [0,φ(λ_Δ)] is at most _1, as g_d,λ'(z')∈ [0,φ(λ_Δ)]. Hence g_d,λ(z)∈ D(_1), which proves the lemma for z_1=z_2=…=z_d=z.

For the general case fix d, let λ∈Λ(_2) and consider x=∏_i=1^d (1+φ^-1(z_i)) for certain z_i∈ D=D(_1).
We want to show that x=∏_i=1^d (1+φ^-1(z)) = (1+φ^-1(z))^d for some z∈ D.
First of all note that

    1+φ^-1(z_i)= exp(exp(z_i)-1/y).

Then

    x=exp( ∑_i=1^d (exp(z_i)-1/y)),

which is equal to (1+φ^-1(z))^d for some z∈ D provided

    1/d∑_i=1^d exp(z_i)=exp(z),

for some z∈ D. Consider the image of D under the exponential map. D is a smoothly bounded domain whose boundary consist of two arbitrarily small half-circles and two parallel horizontal intervals. Recall that the exponential imagine of a disk of radius less than 1 is strictly convex, a fact that can easily be checked by computing that the curvature of its boundary has constant sign. Therefore exp(D) is a smoothly bounded domain whose boundary consists of two radial intervals and two strictly convex curves, hence exp(D) must also be convex. See Figure <ref> for a sketch of the domain D and its image under the exponential map. 
It follows that the convex combination 1/d∑_i=1^d exp(z_i) is contained in the image of D.
In other words, there exists z∈ D such that (<ref>) is satisfied.
This now implies that G_d,λ(z_1,…,z_d)=g_d,λ(z)∈ D, as desired.






 §.§ Proof of Theorem <ref>

We first state and prove a more precise version of Theorem <ref> for the multivariate independence polynomial:

Let Δ∈ℕ with Δ≥ 3. Then for any >0 there exists δ>0 such that for any graph G=(V,E) of maximum degree at most Δ and any λ∈^V satisfying λ_v ∈𝒩([0,(1-)λ_Δ),δ) for each v∈ V, we have that Z_G( λ)≠ 0.


Let _1 and _2 be the two constants from Lemma <ref>, where _1 is chosen sufficiently small.
Let D=D(_1) and let δ=_2.
Let G be a graph of maximum degree at most Δ.
Since the independence polynomial is multiplicative over the disjoint union of graphs, we may assume that G is connected.
Fix a vertex v_0 of G.
We will show by induction that for each subset U⊆ V∖{v_0} we have


  (i) Z_G[U](λ)≠ 0,

  (ii)if u∈ U has a neighbor in V∖ U, then φ(R_G[U],u)∈ D,


Clearly, if U=∅, then both (i) and (ii) are true.

Now suppose U⊆ V∖{v_0} is nonempty and let H=G[U].
Let u_0∈ U be such that u_0 has a neighbor in V∖ U (u_0 exists as G is connected).
Let u_1,…,u_d be the neighbors of u_0 in H. Note that d≤Δ-1.
Define H_0=H-u_0 and set for i=1,…,d H_i=H_i-1-u_i.
Then by induction we know that for i=0,…,d, Z_H_i(λ)≠ 0 and so the ratios R_H_i-1,u_i are well defined for i≥ 1 and by induction they satisfy φ(R_H_i-1,u_i)∈ D.
By Lemma <ref>

    R_H,u_0=λ_u_0/∏_i=1^d(1+R_H_i-1,u_i).

Since φ(R_H_i-1,u_i)∈ D for i=1,…,d, we have by Lemma <ref> that φ(R_H,u_0)∈ D.
From this we conclude that R_H,u_0≠ -1, as -1∉φ^-1(D).
So by (<ref>) Z_H(λ)≠ 0.
This shows that (i) and (ii) hold for all subsets U⊆ V∖{v_0}.

To conclude the proof we need to show that Z_G(λ)≠ 0.

Let v_1,…,v_d be the neighbors of v_0 (in any order). Define G_0=G-v_0 and set for i=1,…,d G_i=G_i-1-v_i.
Then by (i)

we know that for i=0,…,d, Z_G_i(λ)≠ 0 and so the ratios R_G_i-1,v_i are well defined for i≥ 1 and by 
(ii)
they satisfy φ(R_G_i-1,v_i)∈ D. Write for convenience z_i=R_G_i-1,v_i for i=1,…,d.
Then, by the same reasoning as above, we have

    R_G,v_0(1+z_d)=λ_v_0/∏_i=1^d-1(1+z_i)∈φ^-1(D).

This implies that R_G,v_0 is not equal to -1, for if this were the case, we would have
-1∈ z_d+φ^-1(D). However, z_d∈φ^-1(D) and for _1 small enough, φ^-1(D) will have real part bounded away from -1/2,  a contradiction.
We conclude that Z_G(λ)≠ 0.

Theorem <ref> is now an easy consequence.

Let for >0, δ() be the associated δ>0 from Theorem <ref>.
Consider a sequence ϵ_i → 0 and define

    D_Δ:=⋃𝒩([0,(1-_i)λ_Δ),δ(_i)).

The set D_Δ is clearly open and contains [0,λ_Δ).
Moreover, for any graph G of maximum degree at most Δ and λ∈ D_Δ we have Z_G(λ)≠ 0, as λ∈𝒩([0,(1-)λ_Δ),δ()) for some >0.

Let us recall that the literal statement of Theorem <ref> is false in the multivariate setting as we will prove in the appendix.

However, by the same reasoning as above we do immediately obtain the following.

Let Δ∈ℕ with Δ≥ 3, and let n ∈ℕ. Then there exists a complex domain D_Δ containing [0,λ_Δ)^n such that for any graph G=(V,E) with V = {1,… , n} of maximum degree at most Δ and any λ∈ D_Δ, we have that Z_G( λ)≠ 0.

We remark that the difference between Corollary <ref> and Theorem <ref> is subtle. The set D_Δ is chosen of the form

    D_Δ:=⋃𝒩([0,(1-_i)λ_Δ),δ(_i))^n,

as above. In particular the set D_Δ is not of the form D^n for some open set D containing [0,λ_Δ), hence in this sense it is not a literal generalization of Theorem <ref>. 




§ CONCLUDING REMARKS AND QUESTIONS

In this paper we have shown that Sokal's conjecture is true.
By results from <cit.> this gives as a direct application the existence of an efficient algorithm (different than Weitz's algorithm <cit.>) for approximating the independence polynomial at any fixed 0<λ<λ_Δ.
By a result of Sly and Sun <cit.> it is known that unless NP=RP there does not exist an efficient approximation algorithm for computing the independence polynomial at λ>λ_Δ for graphs of maximum degree at most Δ.
Very recently it was shown by Galanis, Goldberg and  Štefankovič <cit.>, building on locations of zeros of the independence polynomial for certain trees, that it is NP-hard to approximate the independence polynomial at λ<-(Δ-1)^Δ-1/Δ^Δ for graphs of maximum degree at most Δ.
Recall from Proposition <ref> that at any λ contained in

    U_Δ-1={λ_Δ(α)=-α (Δ-1)^Δ-1/(Δ-1+α)^Δ| |α|< 1},

the independence polynomial for regular trees does not vanish and that for any λ∈∂(U_Δ-1) there exists λ' arbitrarily close to λ for which there exists a regular tree T such that Z_T(λ')=0.
This naturally leads two the following two questions.

Let α∈ be such that |α|>1. Let >0 and let Δ∈. Is it true that it is NP-hard to compute an -approximation[By an -approximation of Z_G(λ) we mean a nonzero number ζ∈ such that e^-≤ |Z_G(λ)/ζ| ≤ e^ and such that the angle between Z_G(λ) and ζ is at most .] of the independence polynomial at λ_Δ(α) for graphs G of maximum degree at most Δ?

This question has recently been answered positively, in a strong form, by Bezáková, Galanis, Goldberg, and Štefankovič <cit.>. They in fact showed that it is even #P hard to approximate the independence polynomial at non-positive λ contained in the complement of the closure of U_Δ-1.

Is it true that for any graph G of maximum degree at most Δ≥ 3 and any α∈ with |α|<1 one has Z_G(λ_Δ(α))≠ 0?
The same question is also interesting for the multivariate independence polynomial.

We note that if this question too has a positive answer, it would lead to a complete understanding of the complexity of approximating the independence polynomial of graphs at any complex number λ in terms of the maximum degree.




  

Appendix





§ PARABOLIC BIFURCATIONS IN COMPLEX DYNAMICAL SYSTEMS, AND PROPOSITION <REF>


The proof of Proposition <ref> follows from results well known to the complex dynamical systems community, but not easily found in textbooks. In this appendix we give a short overview of the results needed, and outline how Proposition <ref> can be deduced from these results. The presentation is aimed at researchers who are not experts on parabolic bifurcations. Details of proofs will be given only in the simplest setting. Readers interested in working out the general setting are encouraged to look at the provided references.

We consider iteration of the rational function

    f_λ(z) = λ/(1+z)^d,

where λ∈ℂ and d ≥ 2. We note that f_λ has two critical 
points, -1 and ∞, and that f_λ(-1) = ∞.



If f_λ has an attracting or parabolic periodic orbit {x_1, … , x_k}, then the orbits of -1 and ∞ both converge to this orbit.


This statement is the immediate consequence of the following classical result, which can for example be found in <cit.>.


Let f be a rational function of degree d ≥ 2 with an attracting or parabolic cycle. Then the corresponding immediate basin must contain at least one critical point.


Let us say a few words about how  to prove this result in the parabolic case. Recall that a period orbit is called parabolic if its multiplier, the derivative in case of a fixed point, is a root of unity. We consider the model case, where 0 is a parabolic fixed point with derivative 1, and f has the form

    z_1 = z_0 - z_0^2 + h.o.t..

By considering the change of coordinates u = 1/z we obtain

    u_1 = u_0 + 1 + O(1/u_0),

and we observe that if r>0 is chosen sufficiently small, the orbits of all initial values z ∈ D(r,r) ={|z-r|<r} converge to the origin tangent to the positive real axis. In fact, after a slightly different change of coordinates one can obtain the simpler map

    u_1 = u_0 + 1.

These coordinates on D(r,r) are usually denoted by u = ϕ^i(z), and are referred to as the incoming Fatou coordinates. The Fatou coordinates are invertible on a sufficiently small disk D(r,r), and can be holomorphically extended to the whole parabolic basin by using the functional equation ϕ^i(f(z)) = ϕ^i(z) + 1.

By considering the inverse map z_1 = z_0 + z_0^2 + h.o.t. we similarly obtain the outgoing Fatou coordinates ϕ^o, defined on a small disk D(-r,r). It is often convenient to use the inverse map of ϕ^o, which we will denote by ψ^o. This inverse map can again be extended to all of ℂ by using the functional equation ψ^o(ζ-1) = f(ψ^o(ζ)).

Now let f be a rational function of degree at least 2, and imagine that the parabolic basin does not contain a critical point. Then ϕ^i extends to a biholomorphic map from ℂ to the parabolic basin. This gives a contradiction, as a parabolic basin must be a hyperbolic Riemann surface, i.e. its covering space is the unit disk, and therefore cannot be equivalent to ℂ. A similar argument can be given to deduce that any attracting basin must contain a critical point.

Let us return to the original maps f_λ. Recall that for fixed d ≥ 2, we denote the region in parameter space ℂ_λ for which f_λ has an attracting fixed point by U_d. The set U_d is an open and connected neighborhood of the origin. An immediate corollary of the above discussion is the following.


For each λ∈ U_d,  the orbit of the initial value

    z_0 = f^∘ 2_λ(∞) = λ

avoids the point -1.


In fact, it turns out that one can prove the following stronger statement.


The region U_d is a maximal open set of parameters λ for which the orbit of z_0 avoids the critical point -1.


Observe that Lemma <ref> directly implies Proposition <ref>.

Note that the parameters λ for which there is a parabolic fixed point form a dense subset of ∂ U_d. Hence in order to obtain Lemma <ref> it suffices to prove that for any parabolic parameter λ_0 ∈∂ U_d and any neighborhood 𝒩(λ_0), there exists a parameter λ∈𝒩(λ_0) and an N ∈ℕ for which f_λ^∘ N(z_0) = -1. The fact that such λ and N exist is due to the following result regarding parabolic bifurcations.


Let f_ϵ be a one-parameter family of rational functions that vary holomorphically with ϵ. Assume that f = f_0 has a parabolic periodic cycle, and that this periodic cycle bifurcates for ϵ near 0. Denote one of the corresponding parabolic basins by ℬ_f, let z_0 ∈ℬ_f, and let w ∈ℂ̂∖ℰ_f. Then there exists a sequence of ϵ_j → 0 and N_j →∞ for which f_ϵ_j^∘ N_j(z_0) = w.


Here ℰ_f denotes the exceptional set, the largest finite completely invariant set, which by Montel's Theorem contains at most two points; see <cit.>. Since the set {-1,∞} containing the two critical points of the rational functions f_λ: z ↦λ/(1+z)^d  does not contain periodic orbits, it quickly follows that the exceptional set of these functions is empty. Lemma <ref> follows from Theorem <ref> by taking w = -1 and considering a sequence (λ_j) that converges to a parabolic parameter λ_0 ∈∂ U_d.

Perturbations of parabolic periodic points play a central role in complex dynamical systems, and have been studied extensively, see for example the classical works of Douady <cit.> and Lavaurs <cit.>. We will only give an indication of how to prove Theorem <ref>, by discussing again the simplest model, f(z) = z - z^2 + h.o.t., and f_ϵ(z) = f(z) + ϵ^2.  For ϵ≠ 0, the unique parabolic fixed point 0 = f(0) splits up into two fixed points. For ϵ>0 small these two fixed points are both close to the imaginary axis, forming a small “gate” for orbits to pass through.

For ϵ>0 small enough, the orbit of an initial value z_0 ∈ℬ_f, converging to 0 under the original map f, will pass through the gate between these two fixed points, from the right to the left half plane. The time it takes to pass through the gate is roughly π/ϵ. The following more precise statement was proved in <cit.>.


Let α∈ℂ, and consider sequences (ϵ_j) of complex numbers satisfying ϵ_j → 0, and positive integers (n_j) for which

    π/ϵ_j - n_j →α.

Then the maps f_ϵ_j^∘ n_j converge, uniformly on compact subsets of ℬ_f, to the map ℒ_α = ψ^o ∘ T_α∘ϕ^i, where T_α denotes the translation x ↦ x+α.


Let w ∈ℂ̂∖ℰ, and let ζ_0 ∈ℂ for which ψ^o(ζ_0) = w.
Let α∈ℂ be given by

    α = ζ_0 - ϕ^i(z_0)

such that ℒ_α(z_0) = w. Fix ρ>0 small, and for θ∈ [0,2π] write

    α(θ) = α + ρ e^iθ

and

    ϵ_n(θ) = π/α(θ) + n.

It follows that

    f_ϵ_n(θ)^∘ n(z_0) ⟶ℒ_α(θ) := ψ^o ∘ T_α(θ)∘ϕ^i(z_0),

uniformly over all θ∈ [0,2π] as n →∞. Since the curve given by θ↦ℒ_α(θ)(z_0) winds around -1, it follows that for n sufficiently large there exists an α^'_n ∈𝒩(α,ρ) for which

    f_ϵ_n^'^∘ n(z_0) = w

is satisfied for

    ϵ_n^' = π/α_n^' + n.

The general proof of Theorem <ref> follows the same outline.

We end by proving that the literal statement of Theorem <ref> is false in the multivariate setting.


Let Δ≥ 3 and let D_Δ be any neighborhood of the interval [0, λ_Δ). Then there exists a graph G = (V,E) of maximum degree at most Δ and λ∈ D_Δ^V such that Z_G(λ) = 0.


We will in fact use regular trees G for which all vertices on a a given level will have the same values λ_v_i. In this setting we are dealing with a non-autonomous dynamical system given by the sequence

    x_k = λ_k/(1+x_k-1)^Δ-1,

with x_0=0 and where each λ_k ∈ D_Δ. Hence Theorem <ref> is implied by the following proposition.


Given Δ and D_Δ as in Theorem <ref>, there exist an integer N ∈ℕ and λ_0, … ,λ_N ∈ D_Δ which give x_N = -1.


The proof follows from the following lemma, which can be found in <cit.> and is a direct consequence of Montel's Theorem.


Let f be a rational function of degree at least 2, let x lie in the Julia set of f, and let V be a neighborhood of x. Then

    ⋃_n ∈ℕ f^n(V) = ℂ̂∖ℰ_f,

where ℰ_f is the exceptional set of f.


Let Δ≥ 3 and λ≠ 0. As noted before in this appendix, the exceptional set of the function f_Δ-1, λ is empty. Thus, by compactness of the Riemann sphere, it follows that for any neighborhood V of a point in the Julia set there exists an N ∈ℕ such that f_Δ-1, λ^N(V) = ℂ̂.

To prove Proposition <ref>, let us denote the set of all possible values of points x_N by A. Then A contains D_Δ, so in particular a neighborhood V of the parabolic fixed point x_Δ of the function f_Δ-1, λ_Δ.

The parabolic fixed point x_Δ is contained in the Julia set of f_Δ-1, λ_Δ, thus it follows that there exists an N ∈ℕ for which f_Δ-1, λ_Δ^N(V) = ℂ̂. But then f_Δ-1, λ^N(V) = ℂ̂ holds for λ∈ D sufficiently close to λ_Δ, and thus A = ℂ̂. But then -1 ∈ A, which completes the proof of Proposition <ref>.

Note that in this construction the λ_i's take on exactly two distinct values. On the lowest level of the tree they are very close to x_Δ, and on all other levels they are very close to λ_Δ. The thinner the set D_Δ, the more levels the tree needs to have.



§ ACKNOWLEDGEMENT

We thank Heng Guo for pointing out an inaccuracy in an earlier version of this paper.
We moreover thank Roland Roeder and Ivan Chio for helpful comments and spotting some typos. We also thank an anonymous referee for helpful comments.



30
BGKNT7 M. Bayati, D. Gamarnik, D. Katz, C. Nair and P. Tetali, Simple deterministic approximation
algorithms for counting matchings. In Proceedings of the thirty-ninth
annual ACM symposium on Theory of computing (pp. 122–127), ACM, 2007.

B14aA. Barvinok, Computing the permanent of (some) complex matrices, Foundations of Computational Mathematics (2014), 1–14.

B14bA. Barvinok, Computing the partition function for cliques in a graph, Theory of Computing, Volume 11 (2015), Article 13 pp. 339–355.

B15A. Barvinok, Approximating permanents and hafnians of positive matrices, Discrete Analysis, 2017:2, 34 pp.

B17A. Barvinok, Combinatorics and Complexity of Partition Functions,  Algorithms and Combinatorics vol. 30, Springer, Cham, Switzerland, 2017.

BS14aA. Barvinok and P. Soberón, Computing the partition function for graph homomorphisms, Combinatorica 37, (2017), 633–650.

BS14bA. Barvinok and P. Soberón, Computing the partition function for graph homomorphisms with multiplicities, Journal of Combinatorial Theory, Series A, 137 (2016), 1–26.

BGGS17I. Bezakóva, A. Galanis, L.A. Goldberg, and D.Štefankovič, Inapproximability of the independent set polynomial in the complex plane,  arXiv preprint arXiv:1711.00282 (2017).

BLR2010P. Bleher, M. Lyubich and R. Roeder, Lee-Yang zeros for DHL and 2D rational dynamics, I. Foliation of the physical cylinder, Journal de Mathématiques Pures et Appliquées, 107 (2017), 491–590.

BLR2011P. Bleher, M. Lyubich and R. Roeder, Lee-Yang-Fisher zeros for DHL and 2D rational dynamics, II. Global Pluripotential Interpretation. Preprint, available online at arXiv:1107.5764, (2011), 36 pages.

CS7 M. Chudnovsky and P. Seymour, The roots of the independence polynomial of a
clawfree graph, Journal of Combinatorial Theory, Series B, 97 (2007), 350–357.

D94 A. Douady, Does a Julia set depend continuously on the polynomial? Complex dynamical
systems (Cincinnati, OH, 1994), 91–138, Proc. Sympos. Appl. Math., 49, Amer. Math.
Soc., Providence, RI, 1994.

GGS16A. Galanis, L.A. Goldberg, D. Štefankovič, Inapproximability of the independent set polynomial below the Shearer threshold, In LIPIcs-Leibniz International Proceedings in Informatics, vol. 80. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017 (and arXiv preprint arXiv:1612.05832, 2016 Dec 17).

GK12D. Gamarnik and D. Katz: Correlation decay and deterministic FPTAS for counting list-colorings of a graph, Journal of Discrete Algorithms, 12 (2012), 29–47.






L89 P. Lavaurs, Systèmes dynamiques holomorphiques : explosion des points périodiques.
PhD Thesis, Univesité Paris-Sud (1989).

LL15J. Liu, P. Lu, FPTAS for # BIS with degree bounds on one side, in: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing 2015 Jun 14 (pp. 549–556), ACM.

LY13 P. Lu and Y. Yin, Improved FPTAS for multi-spin systems, in: Approximation, Randomization,
and Combinatorial Optimization. Algorithms and Techniques, pp 639–654, Springer Berlin Heidelberg, 2013.

PR16V. Patel, G. Regts, Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials, SIAM Journal on Computing, 46 (2017), 1893–1919.

M06 J. Milnor, Dynamics in one complex variable. Third edition. Annals of Mathematics Studies, 160. Princeton University Press, Princeton, NJ, 2006

R15G. Regts, Zero-free regions of partition functions with applications to algorithms and graph limits, to appear in Combinatorica (2017), https://doi.org/10.1007/s00493-016-3506-7.

SS05A.D. Scott and A.D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, Journal of Statistical Physics, 118 (2005), 1151–1261.

Sh85 J. B. Shearer. On a problem of Spencer, Combinatorica, 5 (1985), 241–245.

S1A. Sokal, A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models, Markov Processes And Related Fields, 7 (2001), 21–38.

SS14Allan Sly and Nike Sun. Counting in two-spin models on d-regular graphs, Annals of Probability, 42 (2014), 2383–2416.

W6D. Weitz, Counting independent sets up to the tree threshold, in Proceedings of the
thirty-eighth annual ACM symposium on Theory of computing, STOC 06, pages 140–149,
New York, NY, USA, 2006. ACM.

