On a conjecture of Sokal concerning roots of the independence polynomial

Introduction

We recall that a set $I\subseteq V$ is called independent if it does not span any edges of $G$. The univariate independence polynomial, which we also denote by $Z_{G}(\lambda)$, is obtained from the multivariate independence polynomial by plugging in $\lambda_{v}=\lambda$ for all $v\in V$.

In statistical physics the univariate independence polynomial is known as the partition function of the hardcore model. When $\lambda=1$, $Z_{G}(\lambda)$ equals the number of independent sets in the graph $G$.

Motivated by applications in statistical physics Sokal [23, Question 2.4] asked about domains of the complex plane where the independence polynomial does not vanish. Just below Question 2.4 in , Sokal conjectures: “there is a complex domain $D_{\Delta}$ containing at least the interval $0\leq\lambda<1/(\Delta-1)$ of the real axis — and possibly even the interval $0\leq\lambda<\lambda_{\Delta}:=\frac{(\Delta-1)^{\Delta-1}}{(\Delta-2)^{\Delta}}$ — on which $Z_{G}(\lambda)$ does not vanish for all graphs of maximum degree at most $\Delta$".

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

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 4.2 in Section 4. We show in Appendix A that the literal statement of Theorem 1.1 does not hold in the multivariate setting.

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

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

Other results for the nonvanishing of the independence polynomial include a result of Shearer that says that for any graph $G=(V,E)$ of maximum degree at most $\Delta$ and any $\lambda$ such that for each $v\in V$, $|\lambda_{v}|\leq\frac{(\Delta-1)^{\Delta-1}}{\Delta^{\Delta}}$ one has $Z_{G}(\lambda)\neq 0$. See for a slight improvement and extensions. Moreover, Chudnovsky and Seymour 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.

Another motivation for Theorem 1.1 comes from the design of efficient approximation algorithms for (combinatorial) partition functions. In Weitz showed that there is a (deterministic) fully polynomial time approximation algorithm (FPTAS) for computing $Z_{G}(\lambda)$ for any $0\leq\lambda<\lambda_{c}(\Delta)$ for any graph of maximum degree at most $\Delta$. 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. . 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. and Barvinok’s recent book . 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 , Barvinok refers to this approach as the interpolation method. Patel and the second author 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 , Theorem 1.1 immediately implies that the interpolation methods yields a polynomial time approximation algorithm for computing the independence polynomial at any fixed $0\leq\lambda<\lambda_{\Delta}$ on graphs of maximum degree at most $\Delta$, thereby matching Weitz’s result. In particular, Theorem 1.1 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\subseteq V$ we denote the graph induced by $U$ by $G[U]$. For $U\subset V$ we denote the graph induced by $V\setminus U$ by $G\setminus U$; in case $U=\{u\}$ we just write $G-u$. For a vertex $v\in V$ we denote by $N[v]:=\{u\in V\mid\{u,v\}\in E\}\cup\{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 $\Delta(G)$.

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 2.3. Section 3 contains technical, yet elementary, derivations needed for the proof of our main result, which is given in Section 4. We conclude with some questions in Section 5. In the appendix we discuss results from complex dynamical systems theory needed to prove Proposition 1.2.

Setup

We will introduce our setup in this section.

Let us define, assuming $Z_{G-v_{0}}(\lambda)\neq 0$,

In the case that $\lambda_{v}>0$ for all $v\in V$ (2) is always defined. This definition is inspired by Weitz . We note that by (1),

So for our purposes it suffices to look at the ratio $R_{G,v_{0}}$.

We now consider the univariate independence polynomial for the trees $T_{\Delta,k}$. Let $v_{k}$ denote the root vertex of $T_{\Delta,k}$. Then for $k>0$, $T_{\Delta,k}-v_{k}$ is equal to the disjoint union of $\Delta-1$ copies of $T_{\Delta,k-1}$. Additionally, for $k>1$, $T_{\Delta,k}\setminus N[v_{k}]$ is equal to the disjoint union of $\Delta-1$ copies of $T_{\Delta,k-1}-v_{k-1}$. Using this we note that for $k>2$ (2) takes the following form:

So (2.1) gives that $R_{T_{\Delta,k},v_{k}}=f_{\Delta-1,\lambda}(R_{T_{\Delta,k-1},v_{k-1}})$. Noting that $R_{T_{\Delta,v_{0}}}=\lambda$, we observe that $R_{T_{\Delta,k},v_{0}}=f_{\Delta-1,\lambda}^{\circ k}(\lambda)$. So to understand under which conditions $R_{T_{\Delta,k},v_{k}}$ equals $-1$ or not, it suffices to look at the orbits of $f_{\Delta-1,\lambda}$ with starting point $\lambda$, 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 and . While here one iteration of $f_{\Delta-1,\lambda}$ corresponds to adding an additional level to a tree, there one iteration corresponded to adding an additional refinement to a hierarchical lattice.

Indeed, writing $f=f_{d,\lambda}$, we note that if $x$ is a fixed point of $f$ we have

A fixed point $x=f(x)$ is attracting if and only if $|f^{\prime}(x)|<1$, which implies the description (5). For parameters $\lambda$ in the boundary $\partial U_{\Delta-1}$ the function $f$ has a neutral fixed point, and for a dense set of parameters $\lambda\in\partial U_{\Delta-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:

We note that for $\lambda=\frac{-(\Delta-1)^{\Delta-1}}{\Delta^{\Delta}}$ part (ii) was proved by Shearer ; see also . 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 2.1 and a counterexample to the multivariate statement of Theorem 1.1, will be discussed in Appendix A. Note that Proposition 1.2 from the introduction is a special case of Proposition 2.1.

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

2 A recursive procedure for ratios for all graphs

It will be convenient to have an expression similar to (2.1) for all graphs. Let $G$ be a graph with fixed vertex $v_{0}$. Let $v_{1},\ldots,v_{d}$ be the neighbors of $v_{0}$ in $G$ (in any order). Set $G_{0}=G-v_{0}$ and define for $i=1,\ldots,d$, $G_{i}:=G_{i-1}-v_{i}$. Then $G_{d}=G\setminus N[v_{0}]$. The following lemma gives recursive relation for the ratios and has been used before over the real numbers in e.g. .

Suppose $Z_{G_{i}}(\lambda)\neq 0$ for all $i=0,\ldots,d$. Then

where in the second equality we use (1). As

As an illustration of Lemma 2.2 we will now prove a result that shows that $Z_{G}(\lambda)$ is nonzero as long as the norms and arguments of the $\lambda_{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 [23, Question 2.4]. The proof moreover serves as warm up for the proof of our main result.

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\subseteq V\setminus\{v_{0}\}$ we have

if $u\in U$ has a neighbor in $V\setminus U$, then |R_{G[U],u}|<\tan\big{(}\frac{\pi}{(2+\varepsilon)(\Delta-1)}\big{)},

if $u\in U$ has a neighbor in $V\setminus U$, then $\Re(R_{G[U],u})>0$.

Clearly, if $U=\emptyset$ both (i), (ii) and (iii) are true. Now suppose $U\subseteq V\setminus\{v_{0}\}$ and let $H=G[U]$. Let $u_{0}\in U$ be such that $u_{0}$ has a neighbor in $V\setminus U$ ($u_{0}$ exists as $G$ is connected). Let $u_{1},\ldots,u_{d}$ be the neighbors of $u_{0}$ in $H$. Note that $d\leq\Delta-1$. Define $H_{0}=H-u_{0}$ and set for $i=1,\ldots,d$ $H_{i}=H_{i-1}-u_{i}$. Then by induction we know that for $i=0,\ldots,d$, $Z_{H_{i}}(\lambda)\neq 0$ and for $i\geq 1$, $\Re(R_{H_{i-1},u_{i}})>0$, implying that $|1+R_{H_{i-1},u_{i}}|\geq 1$. So by Lemma 2.2 we know that

To see that (iii) holds we look at the angle $\alpha$ that $R_{H,u_{0}}$ makes with the positive real axis. It suffices to show that $|\alpha|<\pi/2$. Since by induction $\Re(R_{H_{i-1},u_{i}})>0$ and |R_{H_{i-1},u_{i}}|\leq\tan\big{(}\frac{\pi}{(2+\varepsilon)(\Delta-1)}\big{)}, we see that the angle $\alpha_{i}$ that $1+R_{H_{i-1},u_{i}}$ makes with the positive real axis satisfies $|\alpha_{i}|\leq\frac{\pi}{(2+\varepsilon)(\Delta-1)}.$ This implies by Lemma 2.2 that

As by (iii), $R_{H,u_{0}}$ has strictly positive real part and hence does not equal $-1$ we conclude by (3) that $Z_{H}(\lambda)\neq 0$. So we conclude that (i), (ii) and (iii) hold for all $U\subseteq V\setminus\{v_{0}\}$.

To conclude the proof, it remains to show that $Z_{G}(\lambda)\neq 0$. Let $v_{1},\ldots,v_{d}$ be the neighbors of $v_{0}$. Let $G_{i}$, for $i=0,\ldots,d$, be defined as the graphs $H_{i}$ above. Then by (i) and (ii) we know that for $i=0,\ldots,d$, $Z_{G_{i}}(\lambda)\neq 0$ and $\Re(R_{G_{i-1},v_{i}})>0$ for $i\geq 1$. So as above we have that the angle $\alpha_{i}$, that $1+R_{G_{i-1},v_{i}}$ makes with the positive real line, satisfies $|\alpha_{i}|\leq\frac{\pi}{(2+\varepsilon)\Delta-1}$. So by Lemma 2.2 the absolute value of the argument of $R_{G,v_{0}}$ is bounded by

using that $\frac{\Delta}{\Delta-1}\leq 2$. This implies by (3) that $Z_{G}(\lambda)\neq 0$ and finishes the proof. ∎

To prove Theorem 1.1, we will similarly construct for each $\Delta$ a domain $D$, containing the interval $[0,\lambda_{\Delta}]$ but not the point $-1$, which is mapped inside itself by $f_{d,\lambda}$ for all $0\leq d\leq\Delta-1$ and all $\lambda$ in a sufficiently small complex neighborhood of the interval $[0,(1-\epsilon)\lambda_{\Delta})$. Had these functions $f_{d,\lambda}$ all been strict contractions on the interval $[0,\lambda_{\Delta}]$, the existence of such a domain $D$ would have been immediate. Unfortunately the functions $f_{d,\lambda}$ are typically not contractions, even for real valued $\lambda$. 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 that each $f_{d,\lambda}$ is strictly contracting on $[0,\lambda_{\Delta})$ with respect to the Poincaré metric of the corresponding attracting basin. While these Poincaré metrics vary with $\lambda$ and $d$, this observation does give hope for finding coordinates with respect to which all the maps $f_{d,\lambda}$ are contractions.

In the next section we will introduce explicit coordinates with respect to which $f_{\Delta-1,\lambda_{\Delta}}$ becomes a contraction, and then show that for $d\leq\Delta-1$ and $\lambda\in[0,\lambda_{\Delta})$ the maps $f_{d,\lambda}$ are all strict contractions with respect to the same coordinates. We will then utilize these coordinates to give a proof of Theorem 1.1 in Section 4.

A change of coordinates

It is our aim in this section to find a coordinate change for each $\Delta\geq 3$ so that the maps $f_{d,\lambda}$ are contractions in these coordinates for any $0\leq d\leq\Delta-1$ and any $0\leq\lambda\leq\lambda_{\Delta}$.

with {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y>0}. We note that a similar coordinate change using a double logarithm was used in . 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 $\Delta$ such that the parabolic map $f(x):=f_{\Delta-1,\lambda_{\Delta}}(x)$ becomes a contraction with respect to the new coordinates. Note that we call $f$ parabolic if $\lambda=\lambda_{\Delta}$. In this case the fixed point of $f$ is given by

and has derivative $f^{\prime}(x_{\Delta})=-1$, and is thus parabolic. In the $z$-coordinates we consider the map

Let us start by computing $g^{\prime}$ and $g^{\prime\prime}$. Writing $x_{1}=f(x_{0})$ and $z_{0}=\varphi_{y}(x_{0})$ we note that

and since $\frac{\partial x_{0}}{\partial z_{0}}>0$, we look for points $z_{0}$ where $\frac{\partial g^{\prime}}{\partial x_{0}}(z_{0})=0$. We obtain

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

The only value of $y>0$ for which $g^{\prime\prime}(z_{\Delta})=0$ is given by

Noting that $x_{1}=x_{0}$ and $dx_{1}/(1+x_{1})=1$ when $x_{0}=x_{\Delta}$, we obtain

Thus $g^{\prime\prime}(z_{\Delta})=0$ if and only if

From now on we assume that $y=y_{\Delta}$.

We have that $|g^{\prime}(z)|\leq 1$ for all $z\geq 0$.

it suffices to show that $|g^{\prime}(0)|<1$, which follows if we show that $g^{\prime\prime}(0)<0$, for which it is sufficient to show that $\frac{\partial g^{\prime}}{\partial x_{0}}(0)<0$.

with $x_{1}=f(0)=\lambda$. Hence we can complete the proof by showing that

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

and hence $y>\frac{(d-1)^{2}}{d-1/2}$ . From this we obtain

In particular it follows that for all $x\geq 0$ we have that $f^{\circ n}(x)\rightarrow x_{\Delta}$.

2 Smaller values of λ𝜆\lambda and d𝑑d

We now consider the case where $\lambda<\lambda_{\Delta}$, and the map $f$ has degree $d\leq\Delta-1$. We again consider the map

Again we will often just write $g$ instead of $g_{d,\lambda}$. Our goal is to show that $|g^{\prime}(z_{0})|<1$ for all $z_{0}\geq 0$.

To do so we will consider $g^{\prime}$ as a function of $\lambda,d$ and $z_{0}$. We first look at the case where $\lambda$ is fixed and $d$ is varying.

We will consider the derivative of $g^{\prime}$ with respect to $d$ in the points $z_{0}$ where $g^{\prime\prime}(z_{0})=0$. By (9), $g^{\prime\prime}(z_{0})$ is a multiple of

As $g^{\prime\prime}(z_{0})=0$, we obtain

Now notice that by (7) we have that $\frac{\partial}{\partial d}g^{\prime}$ is a positive multiple of

When we plug in equation (12) to eliminate $x_{0}$ from this expression, we note that the term $(1+x_{1})(1+y\log(1+x_{1}))$ cancels and we obtain that $\frac{\partial}{\partial d}g^{\prime}$ is a positive multiple of

So, we see that as we decrease $d$ the value of $g^{\prime}(z_{0})$ increases and hence it follows that $0\geq g_{d,\lambda}^{\prime}(z_{0})\geq g_{\Delta-1,\lambda}^{\prime}(z_{0})$, as desired. ∎

We next compute the derivative of $g^{\prime}$ with respect to $\lambda$. Note that $x_{1}$ depends on $\lambda$, but $x_{0}$ does not, hence

Thus $\frac{\partial g^{\prime}}{\partial\lambda}(z_{0})=0$ if and only if

Let $\Delta\geq 5$. For any $\lambda\leq\lambda_{\Delta}$ and $0\leq d\leq\Delta-1$, we have

In particular $g^{\prime}(z_{0})$ is decreasing in $\lambda$ for any $z_{0}\geq 0$.

We note that $x_{1}y-(1+y\log(1+x_{1}))$ is increasing in $x_{1}$ for $x_{1}>0$. So it suffices to plug in $\lambda=\lambda_{\Delta}$ and $x_{0}=0$, that is, plug in $x_{1}=\lambda_{\Delta}$. Note that this makes it independent of $d$.

Plugging in $x_{1}=\lambda_{\Delta}$ we get

By a direct computer calculation, we obtain the following approximate values for $c(\Delta)$ for $\Delta\in\{5,6,7\}$:

and we conclude that (14) holds for $\Delta\in\{5,6,7\}$.

Using that $x-x^{2}/2\leq\log(1+x)\leq x$ for all $x\geq 0$, we obtain

Since the right-hand side of (15) is negative for $\Delta=8$ and since the numerator is clearly decreasing in $\Delta$, we conclude that (14) is true for all $\Delta\geq 8$. This concludes the proof. ∎

Let $\Delta\in\{3,4\}$. Let $z_{0}>0$ and $\lambda_{0}>0$ be such that

for $\lambda=\lambda_{0}$. Then $g^{\prime}_{\Delta-1,\lambda_{0}}(z_{0})\geq-0.92$.

By assumption we have $\frac{\partial g^{\prime}(z_{0})}{\partial\lambda}=0$. Thus (13) implies that

This implies that for $x_{1}$ to be a solution to (16), we need that $x_{1}\geq x_{\Delta}$. Indeed suppose that $x_{1}<x_{\Delta}$. Then we have from (16) that

from which we obtain $yx_{1}^{2}>2$. However, as $y<1/x_{\Delta}$ we have $yx_{1}^{2}<yx_{\Delta}^{2}<x_{\Delta}<2$, a contradiction.

Now using that $x_{1}\geq x_{\Delta}$ and by combining (16) and (18) we obtain

where $\alpha_{3}=2+\log(3/2)\approx 2.405$, and where $\alpha_{4}=2+2\log(4/3))\approx 2.575$. This then implies that

Since (17) is decreasing in $x_{0}$ and increasing in $x_{1}$, we can plug in $x_{0}=\alpha_{\Delta}^{-1/(\Delta-1)}(1+x_{\Delta})$ and $x_{1}=\alpha_{\Delta}x_{\Delta}$ to obtain

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

Let $\Delta\geq 3$ and let $\varepsilon>0$. Then there exists $\delta>0$ such that if $0\leq\lambda<(1-\varepsilon)\lambda_{\Delta}$, then $|g^{\prime}_{d,\lambda}(z_{0})|<1-\delta$ for all $z_{0}\geq 0$ and $d\in\{0,1,\ldots,\Delta-1\}$.

Let $J=[0,(1-\varepsilon)\lambda_{\Delta}]$ and let

As for any $\lambda\in J$ we have that $\lim_{z_{0}\to\infty}g^{\prime}_{d,\lambda}(z_{0})=0$ and as $g^{\prime\prime}(0)<0$ by the proof of Corollary 3.2 (which remains valid as (10) is decreasing in $d$) it follows that we may assume that $M$ is attained at some triple $(z_{0},\lambda_{0},d)$ with $z_{0}>0$, $\lambda_{0}\in J$ and $d\in\{0,\ldots,\Delta-1\}$. This then implies that $g_{d,\lambda_{0}}^{\prime\prime}(z_{0})=0$ and hence by Lemma 3.3 we know that $g^{\prime}_{d,\lambda_{0}}(z_{0})\geq g^{\prime}_{\Delta-1,\lambda_{0}}(z_{0})$, that is, we have that $d=\Delta-1$.

If $g^{\prime}_{d,\lambda_{0}}(z_{0})$ attains its minimum (as a function of $\lambda$) at some $\lambda<\lambda_{\Delta}$, then $\frac{\partial}{\partial\lambda}g^{\prime}(z_{0})=0$. So by Lemma 3.4 we know that $\Delta\in\{3,4\}$. Then Lemma 3.5 implies that $M\geq-0.92$. So we may assume that $g^{\prime}$ is strictly decreasing as a function of $\lambda$ on $[0,\lambda_{\Delta}]$. This then implies that $\lambda_{0}=(1-\varepsilon)\lambda_{\Delta}$ and so there exists $\delta>0$ (and we may assume $\delta<0.08$) such that

where the last inequality is by Corollary 3.2. This finishes the proof. ∎

Proof of Theorem 1.1

Let $\Delta\geq 3$ and let $\varepsilon>0$. Then there exist $\varepsilon_{1},\varepsilon_{2}>0$ such that for any \lambda\in\Lambda(\varepsilon_{2}):={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathcal{N}([0,(1-\varepsilon)\lambda_{\Delta}],\varepsilon_{2})}, any $d=0,\ldots,\Delta-1$ and $z_{1},\ldots,z_{d}\in D(\varepsilon_{1})$ we have $G_{d,\lambda}(z_{1},\ldots,z_{d})\in D(\varepsilon_{1})$.

We first prove this for the special case that $z_{1}=z_{2}=\ldots=z_{d}=z$. In this case we have $G_{d,\lambda}(z_{1},\ldots,z_{d})=g_{d,\lambda}(z)$. By Proposition 3.6 we know that there exists $\delta>0$ such that for any $d=0,\ldots,\Delta-1$ we have

By continuity of $g^{\prime}$ as a function of $z$ and $\lambda$ there exists $\varepsilon_{1},\varepsilon_{2}>0$ such that for all $d=0,\ldots,\Delta-1$ and each (z,\lambda)\in D(\varepsilon_{1})\times{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Lambda(\varepsilon_{2})} we have

We may assume that $\varepsilon_{2}$ is small enough so that for any $d$,

Fix now \lambda\in\Lambda{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(\varepsilon_{2})} and $d$ and let $z\in D(\varepsilon_{1})$. Let $z^{\prime}\in[0,\varphi(\lambda_{\Delta})]$ be such that $|z-z^{\prime}|<\varepsilon_{1}$ and let $\lambda^{\prime}\in[0,(1-\varepsilon)\lambda_{\Delta}))$ be such that $|\lambda-\lambda^{\prime}|<\varepsilon_{2}$ Then

implying that the distance of $g_{d,\lambda}(z)$ to $[0,\varphi(\lambda_{\Delta})]$ is at most $\varepsilon_{1}$, as $g_{d,\lambda^{\prime}}(z^{\prime})\in[0,\varphi(\lambda_{\Delta})]$. Hence $g_{d,\lambda}(z)\in D(\varepsilon_{1})$, which proves the lemma for $z_{1}=z_{2}=\ldots=z_{d}=z$.

For the general case fix $d$, let \lambda\in\Lambda({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\varepsilon_{2}}) and consider $x=\prod_{i=1}^{d}(1+\varphi^{-1}(z_{i}))$ for certain $z_{i}\in D=D(\varepsilon_{1})$. We want to show that $x=\prod_{i=1}^{d}(1+\varphi^{-1}(z))=(1+\varphi^{-1}(z))^{d}$ for some $z\in D$. First of all note that

which is equal to $(1+\varphi^{-1}(z))^{d}$ for some $z\in D$ provided

for some $z\in 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 1 for a sketch of the domain $D$ and its image under the exponential map. It follows that the convex combination $\frac{1}{d}\sum_{i=1}^{d}\exp(z_{i})$ is contained in the image of $D$. In other words, there exists $z\in D$ such that (19) is satisfied. This now implies that $G_{d,\lambda}(z_{1},\ldots,z_{d})=g_{d,\lambda}(z)\in D$, as desired. ∎

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

Let $\varepsilon_{1}$ and $\varepsilon_{2}$ be the two constants from Lemma 4.1, where $\varepsilon_{1}$ is chosen sufficiently small. Let $D=D(\varepsilon_{1})$ and let $\delta=\varepsilon_{2}$. Let $G$ be a graph of maximum degree at most $\Delta$. 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\subseteq V\setminus\{v_{0}\}$ we have

if $u\in U$ has a neighbor in $V\setminus U$, then $\varphi(R_{G[U],u})\in D$,

Clearly, if $U=\emptyset$, then both (i) and (ii) are true.

Now suppose $U\subseteq V\setminus\{v_{0}\}$ is nonempty and let $H=G[U]$. Let $u_{0}\in U$ be such that $u_{0}$ has a neighbor in $V\setminus U$ ($u_{0}$ exists as $G$ is connected). Let $u_{1},\ldots,u_{d}$ be the neighbors of $u_{0}$ in $H$. Note that $d\leq\Delta-1$. Define $H_{0}=H-u_{0}$ and set for $i=1,\ldots,d$ $H_{i}=H_{i-1}-u_{i}$. Then by induction we know that for $i=0,\ldots,d$, $Z_{H_{i}}(\lambda)\neq 0$ and so the ratios $R_{H_{i-1},u_{i}}$ are well defined for $i\geq 1$ and by induction they satisfy $\varphi(R_{H_{i-1},u_{i}})\in D$. By Lemma 2.2

Since $\varphi(R_{H_{i-1},u_{i}})\in D$ for $i=1,\ldots,d$, we have by Lemma 4.1 that $\varphi(R_{H,u_{0}})\in D$. From this we conclude that $R_{H,u_{0}}\neq-1$, as $-1\notin\varphi^{-1}(D)$. So by (3) $Z_{H}(\lambda)\neq 0$. This shows that (i) and (ii) hold for all subsets $U\subseteq V\setminus\{v_{0}\}$.

To conclude the proof we need to show that $Z_{G}(\lambda)\neq 0$. Let $v_{1},\ldots,v_{d}$ be the neighbors of $v_{0}$ (in any order). Define $G_{0}=G-v_{0}$ and set for $i=1,\ldots,d$ $G_{i}=G_{i-1}-v_{i}$. Then by (i) we know that for $i=0,\ldots,d$, $Z_{G_{i}}(\lambda)\neq 0$ and so the ratios $R_{G_{i-1},v_{i}}$ are well defined for $i\geq 1$ and by (ii) they satisfy $\varphi(R_{G_{i-1},v_{i}})\in D$. Write for convenience $z_{i}=R_{G_{i-1},v_{i}}$ for $i=1,\ldots,d$. Then, by the same reasoning as above, we have

This implies that $R_{G,v_{0}}$ is not equal to $-1$, for if this were the case, we would have {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-1\in z_{d}+\varphi^{-1}(D)}. However, {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}z_{d}\in\varphi^{-1}(D)} and for $\varepsilon_{1}$ small enough, $\varphi^{-1}(D)$ will have real part bounded away from $-1/2$, a contradiction. We conclude that $Z_{G}(\lambda)\neq 0$. ∎

Let for $\varepsilon>0$, $\delta(\varepsilon)$ be the associated $\delta>0$ from Theorem 4.2. Consider a sequence $\epsilon_{i}\rightarrow 0$ and define

The set $D_{\Delta}$ is clearly open and contains $[0,\lambda_{\Delta})$. Moreover, for any graph $G$ of maximum degree at most $\Delta$ and $\lambda\in D_{\Delta}$ we have $Z_{G}(\lambda)\neq 0$, as $\lambda\in\mathcal{N}([0,(1-\varepsilon)\lambda_{\Delta}),\delta(\varepsilon))$ for some $\varepsilon>0$. ∎

Let us recall that the literal statement of Theorem 1.1 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.

We remark that the difference between Corollary 4.3 and Theorem 1.1 is subtle. The set $D_{\Delta}$ is chosen of the form

as above. In particular the set $D_{\Delta}$ is not of the form $D^{n}$ for some open set $D$ containing $[0,\lambda_{\Delta})$, hence in this sense it is not a literal generalization of Theorem 1.1.

Concluding remarks and questions

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

the independence polynomial for regular trees does not vanish and that for any $\lambda\in\partial(U_{\Delta-1})$ there exists $\lambda^{\prime}$ arbitrarily close to $\lambda$ for which there exists a regular tree $T$ such that $Z_{T}(\lambda^{\prime})=0$. This naturally leads two the following two questions.

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

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 $\lambda$ in terms of the maximum degree.

Appendix A Parabolic bifurcations in complex dynamical systems, and Proposition 2.1

The proof of Proposition 2.1 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 2.1 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

If $f_{\lambda}$ has an attracting or parabolic periodic orbit $\{x_{1},\ldots,x_{k}\}$, then the orbits of $-1$ and $\infty$ both converge to this orbit.

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

Let $f$ be a rational function of degree $d\geq 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 is a parabolic fixed point with derivative $1$, and $f$ has the form

By considering the change of coordinates $u=\frac{1}{z}$ we obtain

and we observe that if $r>0$ is chosen sufficiently small, the orbits of all initial values $z\in 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

These coordinates on $D(r,r)$ are usually denoted by $u=\phi^{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 $\phi^{i}(f(z))=\phi^{i}(z)+1$.

For each $\lambda\in U_{d}$, the orbit of the initial value

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

The region $U_{d}$ is a maximal open set of parameters $\lambda$ for which the orbit of $z_{0}$ avoids the critical point $-1$.

Observe that Lemma A.4 directly implies Proposition 2.1.

Here $\mathcal{E}_{f}$ denotes the exceptional set, the largest finite completely invariant set, which by Montel’s Theorem contains at most two points; see . Since the set $\{-1,\infty\}$ containing the two critical points of the rational functions $f_{\lambda}:z\mapsto\frac{\lambda}{(1+z)^{d}}$ does not contain periodic orbits, it quickly follows that the exceptional set of these functions is empty. Lemma A.4 follows from Theorem A.5 by taking $w=-1$ and considering a sequence $(\lambda_{j})$ that converges to a parabolic parameter $\lambda_{0}\in\partial 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 and Lavaurs . We will only give an indication of how to prove Theorem A.5, by discussing again the simplest model, $f(z)=z-z^{2}+h.o.t.$, and $f_{\epsilon}(z)=f(z)+\epsilon^{2}$. For $\epsilon\neq 0$, the unique parabolic fixed point $0=f(0)$ splits up into two fixed points. For $\epsilon>0$ small these two fixed points are both close to the imaginary axis, forming a small “gate” for orbits to pass through.

For $\epsilon>0$ small enough, the orbit of an initial value $z_{0}\in\mathcal{B}_{f}$, converging to 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 $\pi/\epsilon$. The following more precise statement was proved in .

Then the maps $f_{\epsilon_{j}}^{\circ n_{j}}$ converge, uniformly on compact subsets of $\mathcal{B}_{f}$, to the map $\mathcal{L}_{\alpha}=\psi^{o}\circ T_{\alpha}\circ\phi^{i}$, where $T_{\alpha}$ denotes the translation $x\mapsto x+\alpha$.

such that $\mathcal{L}_{\alpha}(z_{0})=w$. Fix $\rho>0$ small, and for $\theta\in[0,2\pi]$ write

uniformly over all $\theta\in[0,2\pi]$ as $n\rightarrow\infty$. Since the curve given by $\theta\mapsto\mathcal{L}_{\alpha(\theta)}(z_{0})$ winds around $-1$, it follows that for $n$ sufficiently large there exists an $\alpha^{\prime}_{n}\in\mathcal{N}(\alpha,\rho)$ for which

The general proof of Theorem A.5 follows the same outline.

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

Let $\Delta\geq 3$ and let $D_{\Delta}$ be any neighborhood of the interval $[0,\lambda_{\Delta})$. Then there exists a graph $G=(V,E)$ of maximum degree at most $\Delta$ and $\lambda\in D_{\Delta}^{V}$ such that $Z_{G}(\lambda)=0$.

We will in fact use regular trees $G$ for which all vertices on a a given level will have the same values $\lambda_{v_{i}}$. In this setting we are dealing with a non-autonomous dynamical system given by the sequence

with $x_{0}=0$ and where each $\lambda_{k}\in D_{\Delta}$. Hence Theorem A.7 is implied by the following proposition.

The proof follows from the following lemma, which can be found in 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

where $\mathcal{E}_{f}$ is the exceptional set of $f$.

To prove Proposition A.8, let us denote the set of all possible values of points $x_{N}$ by $A$. Then $A$ contains $D_{\Delta}$, so in particular a neighborhood $V$ of the parabolic fixed point $x_{\Delta}$ of the function $f_{\Delta-1,\lambda_{\Delta}}$.

Note that in this construction the $\lambda_{i}$’s take on exactly two distinct values. On the lowest level of the tree they are very close to $x_{\Delta}$, and on all other levels they are very close to $\lambda_{\Delta}$. The thinner the set $D_{\Delta}$, 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.

References