On the Roots of Independence Polynomial: Quantifying the Gap

Let $G=(V,E)$ be a simple undirected graph, that is, without loops and multiple edges, with $V$ representing its set of $n$ vertices and $E$ its set of edges. An independent set of $G$ is a subset of vertices of $V$ such that there is no edge between any pair of vertices in the subset. Let $a_k(G)$ denote the number of independent sets of size $k$ in $G$, where $a_0(G):=1$. Following the convention in [3], we define the independence polynomial

Let $\beta (G)$ denote the smallest real root of $I(G,z)$. It is well known that such a root exists and is indeed in the interval $(0,1]$. Moreover, it is also known that any other root $\rho$ of $I(G,z)$ is strictly greater than $\beta (G)$ in absolute value [5, 3]. We next describe their proofs in brief, but for this we need to introduce some notation.

For a vertex $v\in V$, let $N_G(v)$ denote the set of neighbors of $v$ and $d(v)$ its degree in $G$; we will also use $N(v)$ if $G$ is clear from the context. The set of closed neighbors of $v$ is $N[v]:=N(v)\cup \left\{v\right\}$. Given a subset $S\subset V$, the graph $G\setminus S$ denotes the subgraph of $G$ induced by the vertices $V\setminus S$. A key recursive property of the independence polynomial is the following: For all vertices $u\in V$, we have

One of the key tools used in both [5] and [3] is the Taylor series expansion of $1/I(G,z)$ around the origin. In [5], the vertices of the graph are treated as symbols of an alphabet and the edge relations as congruence relations on the alphabet, that is, if two vertices have an edge then the corresponding alphabets can be swapped in any string. The congruence relations impose an equivalence relation, called the trace monoid, on the set of all finite strings over the alphabet. It is well known that the $n$th coefficient of the power series $1/I(G,z)$ is the number of traces of length $n$ in the monoid. Using the properties of the trace monoid, it is shown that the power series can be expressed as a rational function where both the numerator and denominator correspond to the characteristic polynomial of two positive matrices. Furthermore, the positive matrix that appears in the denominator dominates the one in the numerator entry wise. Therefore, its largest eigenvalue is unique (due to Perron-Frobenius) and it does not appear as an eigenvalue of the numerator. This establishes the uniqueness of the pole, which is also $\beta (G)$. We do not see an immediate way to quantify the proof.

In [3] it is shown, using Equation 1, that the coefficients of the power series $1/I(G,z)$ are all positive. Moreover, from Pringsheim’s theorem we know that the radius of convergence of this power series is $\beta (G)$. Now consider the power series $1/I(H,z)$ for any proper subgraph $H$ of $G$. We can express

By repeated applications of Equation 1, along with induction, one can argue that the coefficients of both $I(H,z)/I(G,z)$ and $1/I(H,z)$ are positive. Therefore, the coefficients of the series on the left-hand side above are greater than the coefficients of $1/I(H,z)$. Hence, . By an inductive argument, it is then shown that $\beta (G)$ is in fact a simple root of $I(G,z)$, when $G$ is connected. To show that any other root $\rho$ of $I(G,z)$ is strictly greater than $\beta (G)$ in absolute value, they consider the function

where $u\in V$. An inductive argument, similar to the one used for $1/I(G,z)$, shows that the coefficients (except the constant coefficient) of this power series are also positive. Now if $\rho$ is any other root of $I(G,z)$ with absolute value $\beta (G)$ then $f_u(\rho )=f_u(|\rho |)=1$, that is, $f_u$ is periodic on the circle $\beta (G)e^{i\theta }$, where $\theta \in [0,2\pi )$ and $i:=\sqrt{-1}$. Using the “Daffodil Lemma” from complex analysis [4, p. 266], this implies that the coefficients of $f_u(z)$ are a subset of an arithmetic progression. However, since the $k$th coefficient of $f_u(z)$ asymptotically is of the form ${(\beta (G\setminus u))}^{-k}$, it does not satisfy an arithmetic progression and this gives us a contradiction that $\rho$ can have the same absolute value as $\beta (G)$. As the proof is by contradiction, it also fails to quantify the gap between $\beta (G)$ and $\rho$.

The insight in this paper builds on the observation that since $f_u(z)$ is holomorphic for all $z$ such that , from the Maximum Modulus Principle [4, p. 545] we know that the largest absolute value of $f_u(z)$ on the disc $D(0,\beta (G)e^{i\theta })$ is attained on its boundary. Moreover, as the coefficients of $f_u(z)$ are positive, a simple calculation shows that the maximum absolute value is attained on the positive real axis, namely at $\beta (G)$. This gives an alternate proof to the ones given above. To quantify this argument, we proceed in two steps: first, we show that the function is univalent in a neighborhood of $\beta (G)$, and second, by constructing a disc around all points with absolute value $\beta (G)$, except in a certain neighborhood of $\beta (G)$, where $f_u(z)$ does not take the value one. The two steps should intuitively hold, since in the case of the former, as the derivative $f_u^{\prime }(z)$ does not vanish at $\beta (G)$ there must be a neighborhood of $\beta (G)$ where the function is injective; the latter case follows from the continuity of $f_u(z)$. The main challenge is to quantify these two intuitive ideas. For this purpose, we need tools, such as, Smale’s $\gamma$-function to study the function locally, and some simple results from complex analysis on radius of univalence of a function, such as $f_u(z)$. The main result of the paper is the following:

In the next section, we describe the main results of the paper with intuitive details. The proofs of these results are developed in the subsequent sections. The necessary preliminary results and definitions from graph theory and complex analysis that are needed are provided in the appendix Appendix A.

Our focus will be to understand the properties of the following function: For any $u\in V$, let

For example, consider the star graph $S_n$ with one central vertex of degree $n$ connected to $n$ leaves. It is not hard to verify that its independence polynomial is ${(1-z)}^n-z$. Now, if $u$ is the “center” vertex in $S_n$ then $f_u(z)=z/{(1-z)}^n$, but if $u$ is one of the leaves in $S_n$ then

If $N[u]=\{u,u_1,\mathrm{\dots },u_k\}$, where $k=d(u)$, then

By $k$ applications of Equation 2, one can recursively construct functions $g_j(z)$, $j=1,\mathrm{\dots },\mathrm{\ell }$ such that

where $g_j(z)$ is not identity for all $j$. Again consider $S_n$ with $u$ as one of the leaves then the function given in Equation 4 can be re-written as

The depth of $f_u(z)$ is one more than the maximum depth of $g_j(z)$’s, where the base case

for $\mathrm{\ell }\ge 1$, has depth one. The example function for $S_n$ with $u$ as a leaf has depth two. The reason why we treat powers of $(1-z)$ in the denominator separately will shortly become clearer.

Now if $\rho$ is a root of $I(G,z)$, then from Proposition A.1 we know that $f_u(\rho )=1$. As mentioned in Section 1, to quantify the gap between $\beta (G)$ and the second smallest absolute value over the remaining roots of $I(G,z)$, involves two steps.

Our first result is to show using Proposition A.2 that $I(G,z)$ is injective in a neighborhood of $\beta (G)$. For this purpose, we define

where $\text{dia}(G)$ is the diameter of $G$ (see Appendix A). We show the following:

We next need to show that for the points on the circle $\beta (G)e^{i\theta }$ that are outside the disc $D(\beta (G),r_G/4)$, there is a disc centered around each of the points such that the value $\left|f_u(z)\right|$ is smaller than one on these discs. The following result makes this precise:

Note that the radius of the disc goes to zero as $\theta$ approaches zero, but this case is already handled in Theorem 2.1. In order to make the bound explicit in terms of graph parameters, we need to upper bound $\left|f_u(\beta e^{i\theta })\right|$ for $\theta$ sufficiently far away from the origin. Ideally one would expect $\left|f_u(\beta e^{i\theta })\right|$ to monotonically decrease in $\theta$ as it varies from $0$ to $\pi$, but this is not the case, as shown in Figure 1 for the function $z/(1-z/{(1-z)}^2)$.

Nevertheless, this is not far away from the truth, since as the depth of $f_u(z)$ increases it concentrates around the origin and drops sharply as $\theta$ increases; we are not able to prove this, but our observation is that it has the properties of a “good kernel” [11]. Instead, we show that there is a natural function that majorizes $\left|f_u(z)\right|$ on the boundary of the disc $D(0,r{e}^{i\theta })$, within its domain of holomorphy, and that is also monotonically decreasing with $\theta$.

A majorant function $G_r(\theta )$ for a complex valued function $g(r{e}^{i\theta })$ satisfies the following two properties:

1. 1.

   $G_r(0)=g(r)$.

2. 2.

   For all $\theta$, $|g(r{e}^{i\theta })|\le G_r(\theta )$, that is, the function majorizes $g$ on the circle $r{e}^{i\theta }$.

3. 3.

   It is a monotone decreasing function, i.e., $G_r^{\prime }(\theta )\le 0$; attains its maximum at the origin, i.e., $G_r^{\prime }(0)=0$; and it is symmetric about the $y$-axis, i.e., $G_r(\theta )=G_r(-\theta )$.

For example, consider the function in the base case $z/{(1-z)}^{\mathrm{\ell }}$. Its absolute value on $r{e}^{i\theta }$ is $r/{|1-r{e}^{i\theta }|}^{\mathrm{\ell }}$, which by a simple calculation turns out to be

In this case it is easier to argue monotonicity because the derivative with respect to $\theta$ is

which is negative for $\theta \in (0,\pi )$. However, we use a simpler majorant function that upper bounds the absolute value in the base case and behaves similarly. Based on the observation that $\left|1-r{e}^{i\theta }\right|\ge 1-r\cos \theta$, one such function is

For $r\le \beta (G-u)$, consider the function

where $j$ varies over some fixed index, and $\mathrm{\ell }\ge 0$. A majorant function $F_{u,r}(\theta )$ for $|f_u(r{e}^{i\theta })|$ is obtained recursively from the majorant functions $G_{j,r}(\theta )$ for $\left|g_j(r{e}^{i\theta })\right|$, respectively, as follows:

The reason we treat powers of $(1-r{e}^{i\theta })$ separately is because if we take the absolute value inside, as we will immanently do for the $g_j$’s, we will get a constant function $r$. So, in principle, we assume that the $g_j$’s have depth more than one.

Let us verify that $F_{u,r}(\theta )$ satisfies all the properties of a majorant function. Firstly,

But as $G_{j,r}(0)=g_j(r)$ and the latter is positive it follows that

Secondly

and thirdly, taking the logarithmic derivative with respect to $\theta$ of $F_{u,r}(\theta )$ we obtain

Therefore, the derivative is non-positive since by induction $G_{j,r}^{\prime }(\theta )\le 0$ and $F_{u,r}(\theta )>0$; moreover, it also vanishes at $\theta =0$, hence, the maximum value is attained at the origin which is equal to $f_u(r)\le 1$, for $r\le \beta (G)$; the symmetric nature also follows by applying induction to Equation 9.

The majorant function will be used in Lemma 2.2 instead of $\left|f_u(\beta e^{i\theta })\right|$. However, we still need a more explicit upper bound on $F_{u,r}(\theta )$. The monotone nature of the function comes to rescue, since locally around the origin we will show that the function is upper bounded by an inverted parabola, that is, $F_{u,r}(\theta )\le F_{u,r}(0)-c{\theta }^2$ for $\theta \le {\theta }_G$ and some constant $c$ dependent on graph parameters. Therefore, the upper bound at ${\theta }_G$ holds for all $F_{u,r}(\theta )$, for $\theta >{\theta }_G$. Substituting this upper bound at ${\theta }_G$ in Lemma 2.2 then gives us the desired explicit disc around every point $\beta e^{i\theta }$ that is devoid of roots. In order to derive this local upper bound, we need to derive an upper bound on a variant of the gamma-function for $F_{u,r}(\theta )$. This is done inductively. Define $F_u(\theta ):=F_{u,\beta (G)}(\theta )$, that is, $F_{u,r}(\theta )$ with $r=\beta (G)$, and $G_j(\theta ):=G_{j,\beta (G)}(\theta )$. Then from Equation 9 it follows that

In particular, we show the following result:

As a consequence, we have

Substituting this in Lemma 2.2, we obtain

Finally, combining this result with Theorem 2.1 gives us Theorem 1.1 as desired.

In the next sections, we develop the proofs and details of the results above.

Throughout this section, we use $\beta :=\beta (G)$, and $v\in V$ as a representative vertex. The function $f_v(z)$ given in Equation 3 can also be expressed as

Then $f_v(\beta )=1$, $f_v(0)=0$, and $f_v^{\prime }(0)=1$. The next result gives a lower bound on the growth of $f_v$ in the vicinity of ${\beta }_G$.

In this section, we prove Lemma 2.2, that is, we show that the gap to unity for every $\theta >{\theta }_G$ is governed by the gap of $f_u(r{e}^{i\theta })$ to $f_u(r)$ and a constant that depends on $r$. We will do the argument only for $r=\beta (G)$. For this purpose, we first need an upper bound on $\left|f_u^{(k)}(\beta (G))\right|$. Again, for convenience, let $\beta :=\beta (G)$.

The $k$th derivative, up to sign, will have the form

Applying Arbogast’s formula Equation 33 we obtain

where the sum is over all indices $i_1,\mathrm{\dots },i_j$ such that

Substituting $z=\beta$ in Equation 18, the term corresponding to $j=k$ disappears in the sum. Plugging the upper bound on the derivatives from Lemma 3.3 in Equation 19 above we get that

From Equation 36, we obtain that $n^{{\sum }_{m}m{i}_m}=n^j$. Moreover, as , we can upper bound its exponent by $k$ as well to get

Using Equation 35 the summation over the indices $i_1,\mathrm{\dots },i_j$ can be expressed as

The last summation over $t$ is the ordered Bell number, ${\tilde{B}}_j$ (see Appendix A), which gives us

Furthermore, applying the upper bound from Equation 38 we derive that

Notice that the summation

Therefore, we finally obtain that

As a consequence, we get that

From this bound, we can derive the following estimate, an alternate proof of Theorem 2.1: