Zero-free regions for the independence polynomial on restricted graph classes
October 01, 2025
Abstract
Generalising the Heilman-Lieb Theorem from statistical physics, Chudnovsky and Seymour [J.Combin.Theory Ser. B, 97(3):350–357] showed that the univariate independence polynomial of any claw-free graph has all of its zeros on the negative real line. In this paper, we show that for any fixed subdivded claw \(H\) and any \(\Delta\), there is an open set \(F \subseteq \mathbb{C}\) containing \([0, \infty)\) such that the independence polynomial of any \(H\)-free graph of maximum degree \(\Delta\) has all of its zeros outside of \(F\). We also show that no such result can hold when \(H\) is any graph other than a subdivided claw or if we drop the maximum degree condition.
We also establish zero-free regions for the multivariate independence polynomial of \(H\)-free graphs of bounded degree when \(H\) is a subdivided claw. The statements of these results are more subtle, but are again best possible in various senses.
1 Introduction↩︎
The hard-core model, a model for the behaviour of gases in equilibrium, is intensely studied across various scientific disciplines, including statistical physics, probability, combinatorics, and theoretical computer science. In the latter two fields, the model is described using the language of independent sets in graphs — the perspective adopted here. Central to this study is the model’s partition function, also known as the independence polynomial, which captures crucial information about both the model and its underlying graph.
The (multivariate) hard-core model is specified by an underlying graph \(G=(V,E)\) together with (complex) weights called fugacities on the vertices \(\boldsymbol{\lambda} = (\lambda_v)_{v \in V} \in \mathbb{C}^V\). For each subset of vertices \(S \subseteq V\), we write \(\lambda_{S} = \prod_{v \in S}\lambda_v\) and we write \(\mathcal{I}(G)\) for the set of all independent sets in \(G\) (i.e., for \(S \subseteq V\), \(S \in \mathcal{I}(G)\) if and only if \(uv \notin E\) for all \(u,v \in S\)). Then the partition function of the hard-core model with respect to \(G\) and \((\lambda_v)_{v \in V}\) is given by \[Z_{G,\boldsymbol{\lambda}} = \sum_{S\in\mathcal{I}(G)} \lambda_S.\] We can equivalently think of \(Z_{G,\boldsymbol{\lambda}}\) as a multivariate polynomial in the (complex) variables \((\lambda_v)_{v \in V}\) called the multivariate independence polynomial of \(G\) and if we set all variables equal so that \(\lambda_v = \lambda\) for all \(v\), we obtain the univariate independence polynomial \(Z_{G,\lambda}\).
This paper presents generalisations of the classical Heilmann-Lieb Theorem [1], a foundational result in statistical physics concerning the (absence of) zeros of the partition function of the monomer-dimer model. The monomer-dimer model is typically described in terms of matchings in graphs, but for our purposes, we describe it here equivalently as a special case of the hard-core model. Given a graph \(H= (U,F)\), the line graph of \(H\) is denoted \(L(H)\) and is defined by \(L(H) = (U',F')\) where \(U' = F\) and \(e,e' \in U' = F\) are adjacent in \(L(H)\) if \(e, e'\) are incident in \(H\). Note that there is a natural correspondence between matchings in \(H\) and independent sets in \(L(H)\). The Heilmann-Lieb Theorem significantly restricts the zeros of the univariate independence polynomial of line graphs.
Theorem 1 (Heilman-Lieb [1]). If \(G\) is a line graph (i.e., \(G = L(H)\) for some \(H\)) then \(Z_{G, \lambda} \not= 0\) for all \(\lambda \in \mathbb{C} \setminus (- \infty, 0)\), i.e., all roots of \(Z_{G, \lambda}\) are negative reals.
It is a well-known fact (and easy to check) that if \(G\) is a line graph, then it is claw free, that is, \(G\) does not contain the claw (the first graph depicted in Figure 1) as an induced subgraph. The class of claw-free graphs is considerably richer than the class of line graphs: indeed there has been considerable effort (see e.g.[2]) to give a constructive description of claw-free graphs from line graphs. Chudnovsky and Seymour [3] generalised the Heilmann-Lieb Theorem to claw-free graphs.
Theorem 2 (Chudnovsky-Seymour [3]). If \(G\) is a claw-free graph then \(Z_{G, \lambda} \not= 0\) for all \(\lambda \in \mathbb{C} \setminus (- \infty, 0)\), i.e., all roots of \(Z_{G, \lambda}\) are negative reals.
The results above restrict the location of zeros in a very strong way showing an absence of zeros on almost the entire complex plane. An important feature of these zero-freeness results is the fact that zeros are restricted away from the positive real line since an absence of zeros around the physically relevant positive real values implies an absence of various types of phase transition (discontinuities in thermodynamic quantities) in the underlying model. In this direction, we completely determine to what extent the Heilman-Lieb Theorem and Chudnovsky-Seymour Theorem above can be generalised to the setting of \(H\)-free graphs for different choices of \(H\).
The subdivided claw \(S_{i,j,k}\) is the graph obtained from the claw by subdividing the three edges \(i-1\), \(j-1\), and \(k-1\) times respectively, so in particular \(S_{1,1,1}\) denotes the claw (see Figure 1 for examples). In naming the subdivided claws, we use the convention \(i\leq j\leq k\). These graphs play a crucial role in the study of independent sets in graph theory [4], [5] and also in our results. Note that if \(G\) is an \(S_{i,j,k}\)-free graph (by which we mean that \(G\) does not contain an induced copy of \(S_{i,j,k}\)), then \(G\) is \(S_{t,t,t}\)-free for any \(t \geq \max(i,j,k)\). We show that there is a zero-free region containing \([0, \infty)\) for the class of bounded-degree \(S_{i,j,k}\)-free graphs (for each fixed choice of \(i,j,k\)).
Theorem 3. Given integers \(t\geq1\) and \(\Delta\geq3\), there exists an open region \(F \subseteq \mathbb{C}\) containing the positive reals \([0, \infty)\) such that if \(G\) is a \(S_{t,t,t}\)-free graph of maximum degree \(\Delta\) and \(\lambda \in F\) then \(Z_{G, \lambda} \not= 0\).
Theorem 3 is best possible in two important ways. Firstly, Theorem 3 does not hold if we replace \(S_{i,j,k}\) with any graph \(H\) that is not a subdivided claw. More precisely, in Section 6, for each \(H\) that is not a subdivided claw (or a path, which might be considered as a degenerate subdivided claw), we exhibit a class of \(H\)-free graphs of maximum degree 3 for which zeros accumulate at some point on the positive real axis. Secondly, Theorem 3 does not hold if we drop the condition that \(G\) has maximum degree \(\Delta\). Indeed, in Section 5 we exhibit a class of graphs that are \(S_{i,j,k}\)-free for all \(i,j \geq 1\) and \(k \geq 2\) (but of unbounded degree) and whose zeros are dense on almost all of \(\mathbb{C}\) including on the positive real line. The only previous result in the direction of Theorem 3 that we are aware of is due to Bencs [6], who showed that the (univariate) independence polynomial of \(S_{1,1,2}\)-free graphs of maximum degree \(\Delta\) have a zero-free sector given by \(|\arg(z)| \leq \pi / \Delta\).
Theorem 3 is in fact derived from a stronger result for the multivariate independence polynomial. The multivariate setting is more subtle even for line graphs and claw-free graphs. For line graphs, Lebowitz, Ruelle, and Speer [7] proved Theorem 4 below using the method of Asano contractions.1 Let \(R(k) \subseteq \mathbb{C}\) be the parabolic region of the complex plane defined by \[R(k) = \Big\{z \in \mathbb{C}: \mathop{\mathrm{Im}}\nolimits(z)^2 < \frac{1}{k}\mathop{\mathrm{Re}}\nolimits(z) + \frac{1}{4k^2}\Big\}.\]
Theorem 4 (Lebowitz-Ruelle-Speer [7]). Suppose \(G=(V,E)\) is a line graph whose largest clique has size at most \(k\) (so the maximum degree of \(G\) is at most \(2k-1\)). If \(\boldsymbol{\lambda} \in R(k^2/4)^V \subseteq \mathbb{C}^V\) then \(Z_{G,\boldsymbol{\lambda}} \not= 0\). The same holds for line graphs of multigraphs (graphs with parallel edges).
Notice that Theorem 4 gives an open multivariate zero-free region containing the positive real line \([0, \infty)\) for line graphs of bounded degree. We give examples in Section 5 that show it is not possible to obtain such multivariate zero-free regions for \(S_{i,j,k}\)-free graphs when \(j,k \geq 2\); however, we come close by giving open multivariate zero-free regions that contain any finite subinterval of \([0, \infty)\).
Theorem 5. Given \(\lambda_0>0\) and integers \(t\geq1\) and \(\Delta\geq3\), there exists an open region \(F \subseteq \mathbb{C}\) containing the interval \([0,\lambda_0]\) such that if \(G=(V,E)\) is a \(S_{t,t,t}\)-free graph of maximum degree \(\Delta\) and \(\boldsymbol{\lambda} \in F^V\) then \(Z_{G, \boldsymbol{\lambda}} \not= 0\).
The proof can be found in Section 3. Of course, the examples for the univariate setting mentioned earlier also show that Theorem 5 cannot hold if we replace \(S_{i,j,k}\) with any graph \(H\) that is not a subdivided claw or if we drop the maximum degree condition.
For \(S_{1,1,k}\)-free graphs, our examples in Section 5 do not preclude the possibility of an open multivariate zero-free region containing the entire positive real line \([0, \infty)\). While we cannot prove the existence of such a region for claw-free graphs, we obtain a result that extends Theorem 4 to a larger class of graphs (that almost includes all claw-free graphs) and that also enlarges the multivariate zero-free region in Theorem 4. We need some notation to describe the result.
A simplicial clique \(K\) in a graph \(G\) is a clique such that for every vertex \(v \in V(K)\), the neighbours of \(v\) outside \(K\) induce a clique in \(G\), that is \(G[\partial v \setminus V(K)]\) is a clique for all \(v \in V(K)\). Write \(\mathcal{G}^{\text{Cl-S}}\) for set of claw-free graphs for which every connected component has a simplicial clique and write \(\mathcal{G}^{\mathrm{Cl-S}}_{k}\) for the set of graphs in \(\mathcal{G}^{\mathrm{Cl-S}}\) whose largest clique has size at most \(k\). The class \(\mathcal{G}^{\mathrm{Cl-S}}\) has been previously studied, e.g., in [8]–[10]. It is also worth noting that given any claw-free graph of bounded degree say \(\Delta\), one can delete at most \(\Delta - 1\) vertices (e.g. delete all but one neighbours of any vertex) to obtain a graph in \(\mathcal{G}^{\mathrm{Cl-S}}\); thus every claw-free graph of bounded degree is very close to a graph in \(\mathcal{G}^{\mathrm{Cl-S}}\). We prove the following in Section 4.
Theorem 6. For any graph \(G \in \mathcal{G}^{\mathrm{Cl-S}}_{k}\) if \(\boldsymbol{\lambda} \in R(k)^V \subseteq \mathbb{C}^V\) then \(Z_{G,\boldsymbol{\lambda}} \not= 0\).
Note that any line graph whose largest clique has size at most \(k\) belongs to \(\mathcal{G}^{\mathrm{Cl-S}}_{k}\) and so Theorem 6 extends Theorem 4 to a larger graph class. Furthermore Theorem 6 gives a multivariate zero-free region \(R(k)\) that matches the \(R(k^2/4)\) in Theorem 4 for \(k=4\), and is larger for \(k>4\). We give examples in Section 5 showing that essentially any multivariate zero-free region for \(\mathcal{G}^{\mathrm{Cl-S}}_k\) must be contained in \(R(k/2)\), so the multivariate zero-free region we give cannot be enlarged by much (if at all).
We point out that from Theorem 3 it follows using Barvinok’s interpolation method [11] together with the results in [12] that there is a deterministic polynomial-time approximation algorithm (specifically a fully polynomial-time approximation scheme) to compute \(Z_{G, \lambda}\) for any \(S_{i,j,k}\)-free graph of maximum degree \(\Delta\) and any \(\lambda \in F\) with \(F\) as given in Theorem 3. Similar algorithms follow from Theorem 5 and Theorem 6. Previously, the second author [13] gave a randomised approximation algorithm for the same computation for positive real values of \(\lambda\) (also in the multivariate setting). This all builds on previous work [14]–[16] that we do not review here.
Related results↩︎
Leake and Ryder [17] consider a weaker form of multivariate zero-freeness called same-phase stability (in which all variables have the same argument) and establish that same-phase stability holds for independence polynomials of all claw-free graphs. They also establish bounds to the closest (univariate) zero for claw-free graphs and graphs in \(\mathcal{G}^{\mathrm{Cl-S}}_{k}\), which Fialho and Procacci [18] recently improved on (in certain settings).
Besides \(H\)-free graphs, there is also considerable interest in the hardcore model on lattices since they often arise in nature. Usually, there is no open zero-free region containing the entire positive real line, but one seeks to bound the zeros in the complex plane e.g.for the square lattices of fixed dimension (and their subgraphs) [19], [20] and hierarchical lattices [21]. Lattices such as the kagome lattice or the pyrochlore lattice are in fact line graphs so that the Heilman-Lieb Theorem already applies.
For certain classes of trees, Bencs [22] showed real rootedness of the independence polynomial. The class of general trees of bounded degree has received considerable attention because, as it turns out, the zeros of trees of maximum degree \(\Delta\) coincide exactly with zeros of general graphs of maximum degree \(\Delta\) (see e.g.[22]). In this direction, Dobrushin [23], [24] and Shearer [25] independently established a zero-free disc for graphs of maximum degree \(\Delta\) that is centered at zero of radius \(\lambda_s(\Delta) = (\Delta - 1)^{\Delta -1}/ \Delta^{\Delta}\). While this zero-free disc cannot be enlarged in the negative direction, in the positive real direction, Peters and Regts [26] found a zero-free region that contains a neighbourhood of the interval \([0, \lambda_c(\Delta))\), where \(\lambda_c(\Delta) = (\Delta - 1)^{\Delta -1} / (\Delta - 2)^{\Delta} > \lambda_s(\Delta)\) thus resolving a conjecture of Sokal [27]. This began a sequence of works which together show that, for graphs of maximum degree \(\Delta\), there is a cardioid region \(C_{\Delta} \subseteq \mathbb{C}\) (that intersects \(\mathbb{R}\) in the interval (\(-\lambda_s(\Delta)\), \(\lambda_c(\Delta)\))) outside of which zeros of the independence polynomial are dense [28], [29] but inside of which there are both zeros [30] and zero-free regions [31] suggesting an exact description might be difficult to give (although there is an understanding of the limiting behaviour [32]).
2 Notation↩︎
For a graph \(G=(V,E)\) and a vertex \(v \in V\), we write \(\partial v\) for the neighbours of \(v\) in \(G\). For \(U\subseteq V\), we write \(\partial U=\{v\in V\setminus U:v \in \partial u \text{ for some }u\in U\} = (\cup_{u \in U} \partial u) \setminus U\) for the boundary of \(U\). We write \(G[U]\) for the graph induced by \(G\) on \(U\). We write \(U^{(\leq r)} := \{S \subseteq U: |S| \leq r\}\).
We recall and extend some notation from the Introduction. Given complex vertex weights \(\boldsymbol{\lambda}=(\lambda_v)_{v\in V} \in \mathbb{C}^V\) and \(S \subseteq V\), we write \(\lambda_{S} = \prod_{v \in S}\lambda_v\). We write \(\mathcal{I}(G)\) for the set of all independent sets in \(G\). Then the (multivariate) independence polynomial of \(G\) is \[Z_{G,\boldsymbol{\lambda}} = \sum_{S\in\mathcal{I}(G)} \lambda_S.\] As the graph \(G\) remains fixed most of the time, we generally use the abbreviated forms \(\mathcal{I}(U)=\mathcal{I}(G[U])\) and \(Z(U) = Z_{G[U],\boldsymbol{\lambda}[U]}\), where \(\boldsymbol{\lambda}[U]\) are the weights inherited from \(G\) by \(G[U]\).
Recall that for \(1\leq i\leq j\leq k\), we write \(S_{i,j,k}\) for the subdivided claw whose leaves are at distance \(i\), \(j\) and \(k\) from the degree-3 vertex (see Figure 1). Note that the class of \(S_{i,j,k}\)-free graphs is contained in the class of \(S_{t,t,t}\)-free graphs, where \(t=\max\{i,j,k\}\), so we lose little in what follows by focusing on symmetric subdivided claws.
3 Zero-free regions for graphs with no induced subdivided claw↩︎
Given a graph \(G=(V,E)\) together with a fixed root vertex \(u \in V\), we define admissible pairs of vertex subsets recursively as follows. For \(L, U \subseteq V\), we define \((L,U)\) to be admissible (with respect to \(G, u\)) if \((L,U)\) satisfies
\((L,U) = (\emptyset, V)\); or
\((L,U) = (\{ u \}, V \setminus \{ u \})\); or
\(L\) is an independent set satisfying \(\emptyset \not= L \in \mathcal{I}(\partial L' \cap U')\) and \(U = U' \setminus \partial L'\) for some admissible pair \((L',U')\).
We use the unusual convention that \(\partial \emptyset = \{ u \}\) in order to omit the second item above and streamline our inductive argument. It is easy to see that \(U \cap L = \emptyset\) for any admissible pair \((L,U)\) and so \((L,V)\) is admissible if and only if \(L = \emptyset\); this is a fact we use later. See Figure [fig:admissible] for an illustration of the inductive step (third bullet point above) in the definition of admissible pair.
The introduction of admissible pairs is motivated by a process used in [13] to sample red-blue pairs of random independent sets in \(G\). The union \(R\cup B\) of independent sets \(R\) and \(B\) induces connected components in the graph \(G\). The inductive definition of admissible pairs given above mirrors the process of growing the red-blue connected component from a distinguished vertex \(u\), presented in [13].
Our approach to proving non-vanishing of the partition function is an induction over pairs \((L,U)\) of vertex subsets. The admissible pairs arise as the pairs \((L,U)\) that appear in that inductive argument. The usage here may seem quite different to that in [13], but the crucial property of \(S_{t,t,t}\)-free graphs that we rely on is the same, namely that \(|L|\) remains bounded. (For general graphs with degree-bound \(\Delta\) the set \(L\) may grow unceasingly.) The following is a restatement of Lemma 14 of [13].
Lemma 1. Let \(G\) be a graph of maximum degree \(\Delta\) that is \(S_{t,t,t}\)-free. If \((L,U)\) is an admissible pair then \(|L| \leq 2 \mathop{\mathrm{vol}}(\Delta, 2t)\), where \[\mathop{\mathrm{vol}}(\Delta, t) := 1 + \Delta \frac{(\Delta - 1)^t - 1}{\Delta - 2}.\]
Our goal is to show that \(Z_{G,\boldsymbol{\lambda}} = Z(V)\) is non-zero for \(S_{t,t,t}\)-free graphs \(G=(V,E)\) when the complex weights \(\boldsymbol{\lambda}\) are close to the positive real line. The first lemma establishes invariant regions of the complex plane under complex transformations that arise as recursions in our induction proof. Recall that we write \(R(k) \subseteq \mathbb{C}\) for the parabolic region in the complex plane given by \[\label{eq:parabola} R(k) = \Big\{z \in \mathbb{C}: \mathop{\mathrm{Im}}\nolimits(z)^2 < \frac{1}{k}\mathop{\mathrm{Re}}\nolimits(z) + \frac{1}{4k^2}\Big\}.\tag{1}\] Similarly, write \(H(t)\) for the halfplane in \(\mathbb{C}\) given by \[H(t) = \{z \in \mathbb{C}: \mathop{\mathrm{Re}}\nolimits(z) \geq t\}.\]
Lemma 2. Fix \(\mathbf{a} = (a_1, \ldots, a_k) \in R(k)^k\) and consider the complex function \(f_{\mathbf{a}}: \mathbb{C}^k \rightarrow \mathbb{C}\) given by \(f_{\mathbf{a}}(z_1, z_2, \ldots, z_k) = 1 + \sum_{j=1}^k a_jz_j^{-1}\). Then \(f_{\mathbf{a}}(H(1/2)^k) \subseteq H(1/2)\).
Proof. Given \(\mathbf{z} = (z_1, \ldots, z_k) \in H(1/2)^k\), we have for each \(j\) that \(z_j^{-1}\) lies inside the disc centered at \(1\) of radius \(1\) and so \(a_jz_j^{-1}\) lies in the disc centered at \(a_j\) of radius \(|a_j|\). The leftmost point of this disc has real part \(\mathop{\mathrm{Re}}\nolimits(a_j) - |a_j|\) and furthermore, by our choice of \(a_j\), we have \[\begin{align} \mathop{\mathrm{Re}}\nolimits(a_j) - |a_j| &= \mathop{\mathrm{Re}}\nolimits(a_j) - (\mathop{\mathrm{Re}}\nolimits(a_j)^2 + \mathop{\mathrm{Im}}\nolimits(a_j)^2)^{1/2} \\ &\geq \mathop{\mathrm{Re}}\nolimits(a_j) - \big(\mathop{\mathrm{Re}}\nolimits(a_j)^2 + \mathop{\mathrm{Re}}\nolimits(a_j)/k + (1/2k)^2\big)^{1/2} = -1/2k. \end{align}\] This shows that \(\mathop{\mathrm{Re}}\nolimits(a_jz_j^{-1}) \geq -1/2k\) and so \(\mathop{\mathrm{Re}}\nolimits(f_{\mathbf{a}}(z_1, \ldots, z_k)) \geq 1/2\), i.e., \(f_{\mathbf{a}}(\mathbf{z}) \in H(1/2)\). ◻
Lemma 3. Fix positive integers \(t, \Delta\) and let \(r = 2\mathop{\mathrm{vol}}(\Delta, 2t)\). For any \(S_{t,t,t}\)-free graph \(G=(V,E)\) of maximum degree \(\Delta\), any complex vertex weights \(\boldsymbol{\lambda}=(\lambda_v)_{v \in V}\) satisfying \(\lambda_S \in R(2^{\Delta r})\) for all \(S \in V^{(\leq r)}\), any root vertex \(u \in V\), and any admissible pair \((L,U)\), we have
\(Z(U), Z(U \setminus \partial L) \not= 0\);
\(Z(U) / Z(U \setminus \partial L)) \in H(1/2)\).
In particular \(Z_{G,\boldsymbol{\lambda}} \not= 0\) by taking the admissible pair \((\emptyset, V)\).
Proof. We prove the lemma by induction on \(|U| + |G|\). For the base case, when \((L,U) = (L,\emptyset)\), we have \(Z(U) = Z(U \setminus \partial L) = 1\) and (i) and (ii) immediately follow.
For the induction step, suppose we are given an admissible pair \((L,U)\) (with respect to \(G,u\)) with \(|U| \geq 1\). We have the following recursion: \[Z(U) = Z(U \setminus \partial L) + \sum_{\emptyset \not= S \in \mathcal{I}(U \cap \partial L)} \lambda_S Z(U \setminus (\partial L \cup \partial S)).\] Note that \(Z(U \setminus \partial L) \not= 0\) by induction using (i) by considering the admissible pair \((\emptyset, U \setminus \partial L)\) with respect to the smaller2 graph \(G[U \setminus \partial L]\) and any root vertex \(u' \in U \setminus \partial L\). Therefore, we can divide through by \(Z(U \setminus \partial L)\) to obtain \[\label{jfktombr} \frac{Z(U)}{Z(U \setminus \partial L)} = 1 + \sum_{\emptyset \not= S \in \mathcal{I}(U \cap \partial L)} \lambda_S \left( \frac{Z(U \setminus \partial L)}{Z(U \setminus (\partial L \cup \partial S))} \right)^{-1}.\tag{2}\]
If \(U \cap \partial L = \emptyset\) then \(U = U \setminus \partial L\) and so \(Z(U) = Z(U \setminus \partial L) \not= 0\) (as established above) from which (i) and (ii) follow. If \(U \cap \partial L \not= \emptyset\), then for any nonempty \(S\in\mathcal{I}(U \cap \partial L)\), the pair \((S, U \setminus \partial L)\) is admissible (by definition). Therefore \(Z(U \setminus (\partial L \cup \partial S)) \not= 0\) by induction (i) and \(\frac{Z(U \setminus \partial L)}{Z(U \setminus (\partial L \cup \partial S))} \in H(1/2)\) by induction (ii). Recall from Lemma [lem:1dstructure] that \(|L| \leq r = 2\mathop{\mathrm{vol}}(\Delta, 2t)\) and so \(|\partial L| \leq \Delta r\); this means the sum above has at most \(2^{\Delta r}\) terms. (This is a loose bound; a better one would follow from noting that \(|S|\leq r\)). By our choice of \(\boldsymbol{\lambda}\) and noting \(|S| \leq r\) (by Lemma [lem:1dstructure]), we have \(\lambda_S \in R(2^{\Delta r})\). Applying Lemma 2 to [eq:recursion] shows (ii). From this (i) follows. ◻
As noted in the Introduction, we cannot obtain a multivariate zero-free region containing \((0, \infty)\), but we can get such a univariate zero-free region, and also an open multivariate zero-free region containing any finite interval of the positive real axis.
First, to obtain the univariate zero-free region, we specialise Lemma 3 to the admissible pair \((\emptyset,V)\) and the constant weighting where \(\lambda_v = \lambda\) for all \(v \in V\).
Proof of Theorem 3. We are given positive integers \(t, \Delta\). Let \(r = 2\mathop{\mathrm{vol}}(\Delta, 2t)\) and let \(F= \{\lambda \in \mathbb{C} : \mathop{\mathrm{Re}}\nolimits(\lambda) \geq 0 \text{ and } \lambda^r \in R(2^{\Delta r})\}\). For any \(S_{t,t,t}\)-free graph \(G = (V,E)\) of maximum degree \(\Delta\) and any \(\lambda \in F\), setting \(\lambda_v = \lambda\) for all \(v \in V\), we have \(\lambda_S \in R(2^{\Delta r})\) for any \(S \in V^{(\leq r)}\). Thus we can apply Lemma 3 to conclude \(Z_{G, \lambda} \not= 0\). ◻
Remark 7. We derive a slightly smaller but more explicit zero-free region. For the set \(F\) defined in the proof above, we have \[F \supseteq F^* = \left\{ (x+\mathrm{i}y): |y| \leq 2^{-\frac{1}{2}(\Delta + 3) r}x^{1 - \frac{1}{2}r}, x \geq 2^{-\Delta} \right\}.\] To see this, note that if \(z = x+\mathrm{i}y \in F^*\) then \(x \geq 2^{-\Delta} \geq 2|y|\) so \[|\mathop{\mathrm{Im}}\nolimits(z^r)| = |\mathop{\mathrm{Im}}\nolimits((x+\mathrm{i}y)^r)| = \left| \sum_{t \text{ odd}}^r \binom{n}{t}(\mathrm{i}y)^tx^{r-t} \right| \leq \sum_{t \text{ odd}}^r \binom{n}{t}|y|x^{r-1} \leq 2^r|y|x^{r-1},\] and \(|\mathop{\mathrm{Re}}\nolimits(z^r)| \geq (x - |y|)^r \geq (\frac{1}{2}x)^r\). Now it is easy to check that \(z^r \in R(2^{\Delta r})\). Note that close to the origin, we know the disc of radius \((\Delta - 1)^{\Delta - 1}/ \Delta^{\Delta} \approx e/ \Delta\) is zero-free (see the Introduction) and this disc intersects \(F^*\).
Finally, we come to the existence of multivariate zero-free regions including arbitrary finite intervals of the positive real axis.
Proof of Theorem 5. Without loss of generality, assume \(\lambda_0\geq1\). Fix \(\varepsilon>0\) and choose \(\psi>0\) such that the bounded sector \[F=\{z:|z|<\lambda_0+\varepsilon\text{ and } |\arg z|<\psi\}\] is such that \(\{z^r:z\in F\}\subseteq R(2^{\Delta r})\). Then, by Lemma 3, \(F\) is a multivariate zero-free region for \(Z_{G,\boldsymbol{\lambda}}\). ◻
4 Claw-free graphs↩︎
We begin this section with some structural properties of claw-free graphs. Recall that a simplicial clique in a claw-free graph \(G\) is a clique \(K\) in \(G\) such that for every vertex \(v \in V(K)\), \(G[\partial v \setminus K]\) is a clique. Recall that \(\mathcal{G}^{\mathrm{Cl-S}}\) is the set of claw-free graphs whose every component has a simplicial clique and \(\mathcal{G}^{\mathrm{Cl-S}}_k\) is the set of graphs in \(\mathcal{G}^{\mathrm{Cl-S}}\) whose largest clique has size at most \(k\). We will require the following (perhaps surprising) structural lemma, which we believe is new since the authors of [8] investigate structural properties of the graph class \(\mathcal{G}^{\mathrm{Cl-S}}\) but do not mention that it is hereditary.
Lemma 4. If \(G \in \mathcal{G}^{\mathrm{Cl-S}}\) and \(X \subseteq V(G)\) then \(G' = G[V(G) \setminus X] \in \mathcal{G}^{\mathrm{Cl-S}}\), i.e.\(\mathcal{G}^{\mathrm{Cl-S}}\) is a hereditary graph class.
Proof. It is sufficient to prove the lemma in the case that \(X=\{v\}\) is a single vertex and \(G\) is connected. Let \(K\) be a simplicial clique of \(G\). We distinguish two cases, depending on whether or not \(G'\) is connected.
Suppose first that removing vertex \(v\) separates \(G\) into \(k\) connected components \(G_1,\ldots, G_k\), with \(k\geq2\). Then, for all \(i\in\{1,\ldots,k\}\) the vertex subset \(U=\partial v\cap V(G_i)\) induces a clique. (Suppose \(u,u'\in U\) and \(w\in \partial v \cap V(G_j)\) with \(j \not= i\). Then \(uu'\) must be an edge, otherwise \(\{v,u_,u',w\}\) would induce a claw.) Also, \(U\) must be simplicial in \(G_i\). (Suppose \(u\in U\) and \(w,w'\in \partial u \cap(V(G_i)\setminus U)\). Then \(ww'\) is an edge, otherwise \(\{u,v,w,w'\}\) would induce a claw.)
The other possibility is that \(G'=G-v\) is connected. If \(v\notin K\) then the clique \(K\) remains simplicial. If \(v\in K\) and \(|K|\geq2\) then \(K-v\) is a simplicial clique in \(G'\). Finally, if \(K=\{v\}\), then \(U= \partial v\) is a clique (since \(K\) is simplicial) and \(U\) is simplicial in \(G'\) (otherwise there would be vertices \(u\in U\) and \(w,w'\in \partial u \setminus (U\cup \{v\})\) such that \(\{u,v,w,w'\}\) induces a claw. ◻
Next we require some notation on paths. Let \(G\) be a graph and \(P\) be a path in \(G\) with \(|V(P)| \geq 1\). Let \(u\) and \(x\) be the endpoints of \(P\) (where we allow \(u=x\) when \(P\) has a single vertex). When working with any path, we specify one of its endpoints to be active and we indicate that \(x\) is the active vertex by writing \(Px\) (and in the case when \(P\) has one vertex, that vertex is taken to be active). We define \[A_{Px}(G) = V(P) \cup \partial(V(P) \setminus \{x\})\] and \[U_{Px}(G) = V(G) \setminus A_{Px}.\] We simply write \(A_{Px}\) and \(U_{Px}\) when \(G\) is clear from context. Given \(Px\) in \(G\) and \(y \in \partial x \cap U_{Px}\), then we write \(Pxy\) for the path \(P\) with vertex \(y\) appended to \(x\) and where \(y\) is now the active vertex. All paths we consider have at least one vertex.
We give one further piece of notation on simplicial cliques. For a claw-free graph \(G\) with a simplicial clique \(K\), we write \(G + u_K\) for the graph obtained from \(G\) by adding a new vertex \(u_K\) that is adjacent to every vertex in \(K\). It is easy to check that \(G + u_K\) is claw-free and we call \(u_K\) the artificial simplicial vertex, which is a natural starting point for our paths in the next lemma.
Lemma 5. For any \(G = (V,E) \in \mathcal{G}_k^{\mathrm{Cl-S}}\) with a simplicial clique \(K\), any path \(Px\) in \(G + u_K\) starting at the artificial simplicial vertex \(u_K\) and ending at \(x\) (where we allow \(x=u_K\)), and any complex vertex weights \(\boldsymbol{\lambda}=(\lambda_v)_{v \in V} \in R(k)^V \subseteq \mathbb{C}^V\) we have
\(Z(U_{Px}), Z(U_{Px} \setminus \partial x) \not= 0\) and
\(\mathop{\mathrm{Re}}\nolimits(Z(U_{Px}) / Z(U_{Px} \setminus \partial x) ) \geq 1/2\).
The partition function \(Z\) in the lemma above is with respect to the graph \(G + u_K\), but note that since our path always includes the vertex \(u_K\) as a starting point, then \(U_{Px}\) always excludes \(u_K\), so we do not need to specify a weight for \(u_K\).
Proof of Lemma 5. We do induction on \(|U_{Px}| + |G + u_K|\). If \(|U_{Px}|=0\) then \(Z(U_{Px})= Z(U_{Px} \setminus \partial x) = 1\) and both (i) and (ii) immediately follow.
For the induction step first consider the case \(U_{Px} \cap \partial x = \emptyset\). We see that (ii) follows immediately provided (i) holds. For (i), note that \(U_{Px} \cap \partial x = \emptyset\) can only happen if \(|V(Px)| \geq 2\), in which case \(G' = G[U_{Px}]\) is strictly smaller than \(G\) and every component of \(G'\) has a simplicial clique by Lemma [lem:simplicial]. By applying induction to each of those components, we have \(Z(U_{Px}) \not= 0\) so (i) follows. Thus we may assume \(U_{Px} \cap \partial x \not= \emptyset\).
Now assuming \(U_{Px} \cap \partial x \not= \emptyset\), let us check that \(U_{Px} \cap \partial x\) induces a clique in \(G\). If \(|V(Px)| = 1\) then \(P\) consists of the single simplicial vertex \(x = u_K\), so \(\partial x\) induces a clique. If \(|V(Px)| \geq 2\) and \(a,b \in U_{Px} \cap \partial x\) are non-adjacent then \(\{ x^-, x, a, b \}\) induces a claw in \(G\) where \(x^-\) is the predecessor of \(x\) on \(P\) (a contradiction). Hence \(U_{Px} \cap \partial x\) induces a clique (of size at most \(k\)), and we have \[Z(U_{Px}) = Z(U_{Px} \setminus \partial x) + \sum_{y \in U_{Px} \cap \partial x}\lambda_y Z(U_{Px} \setminus (\partial x \cup \partial y)).\] Note that \(U_{Px} \setminus \partial x = U_{Pxy}\) for any \(y\) adjacent to \(x\) and so by induction (using (i)), we have \(Z(U_{Px} \setminus \partial x) = Z(U_{Pxy}) \not= 0\), so we can divide the recursion above by this quantity to obtain \[\begin{align} \frac{Z(U_{Px})}{Z(U_{Px} \setminus \partial x)} &= 1 + \sum_{y \in U_{Px} \cap \partial x}\lambda_y \left( \frac{Z(U_{Px} \setminus \partial x)}{Z(U_{Px} \setminus (\partial x \cup \partial y))} \right)^{-1} \\ &= 1 + \sum_{y \in U_{Px} \cap \partial x}\lambda_y \left( \frac{Z(U_{Pxy})}{Z(U_{Pxy} \setminus \partial y)} \right)^{-1}. \end{align}\] By induction, we may assume that \(\mathop{\mathrm{Re}}\nolimits\left( \frac{Z(U_{Pxy})}{Z(U_{Pxy} \setminus \partial y)} \right) \geq 1/2\) and so by our choice of \(\boldsymbol{\lambda}\), Lemma 2 says that \(\mathop{\mathrm{Re}}\nolimits(\frac{Z(U_{Px})}{Z(U_{Px} \setminus \partial x)}) \geq 1/2\) proving (ii). This also immediately implies (i) (the second part of which was established earlier). ◻
Proof of Theorem 6. This follows from Lemma 5 by taking \(x=u_K\), and hence \(V(P)=\{x\}\) and \(U_{Px}=V(G)\). ◻
5 Examples↩︎
In this section we give examples showing the various ways in which it is not possible to extend the results we have presented so far. We will consider examples from larger and larger graph classes:
\[\begin{align} \text{line graph}&\subset\text{line graph of a multigraph}\\ &\subset\text{claw-free graph with a simplicial clique}\\ &\subset\text{claw-free graph}\\ &\subset\text{E-free graph, i.e., S_{1,2,2}-free}. \end{align}\]
5.1 Even cycles↩︎
Let \(C_{2n}\) denote the even cycle with vertex set \(V(C_{2n})=[2n]=\{0,1,\ldots,2n-1\}\) and edge set \(E(C_{2n})=\{ij:j=i+1\pmod{2n}\}\). Many of our examples will be based on (even) cycles so we need to locate some of the multivariate zeros of \(Z_{C_{2n},\boldsymbol{\lambda}}\). Since \(C_{2n}\) is a line graph, Theorem 4 with \(k=2\) asserts that \(R(1)\) is a multivariate zero-free region. We show that this region cannot be extended further. Denote by \(B(z,\varepsilon)\) the disc of radius \(\varepsilon\) about \(z\).
Lemma 6. Suppose \(z_0\in\partial R(1)\) and \(\varepsilon>0\). Then there exist \(n\in\mathbb{N}\), \(z\in B(z_0,\varepsilon)\) and \(\boldsymbol{\lambda}:V(C_{2n})\to\{z,\bar z\}\) such that \(Z_{C_{2n},\boldsymbol{\lambda}}=0\).
Proof. Define \(\boldsymbol{\lambda}:V(C_{2n})\to\mathbb{C}\) by \[\lambda_i=\begin{cases} \lambda,&\text{if i is even;}\\ \mu,&\text{if i is odd.} \end{cases}\] A convenient way of keeping track of the calculation of \(Z_{C_{2n,\boldsymbol{\lambda}}}\) is using a ‘transfer matrix’. Consider a path \(P_2\) of length 2 whose vertices, taken in order, have weights 1, \(\mu\) and \(\lambda\). Define \[M=\begin{pmatrix}m_{00}&m_{01}\\m_{10}&m_{11}\end{pmatrix}=\begin{pmatrix}1&0\\0&\lambda\end{pmatrix} \begin{pmatrix}1&1\\1&0\end{pmatrix} \begin{pmatrix}1&0\\0&\mu\end{pmatrix} \begin{pmatrix}1&1\\1&0\end{pmatrix} =\begin{pmatrix}\mu+1&1\\\lambda&\lambda\end{pmatrix}.\] Note that \(Z_{P_2,(1,\mu,\lambda)}=m_{00}+m_{01}+m_{10}+m_{11}\), and that \(m_{00}\) is the contribution to the partition function from independent sets excluding both ends of \(P_2\), that \(m_{01}\) is the contribution of independent sets including the left endpoint of \(P_2\) and excluding the right, and so on. The transfer matrix for a path of length \(2n\) with weights \((1,\mu,\lambda,\ldots,\mu,\lambda)\) is then simply \(M^n\). Finally, the partition function for a cycle of length \(2n\), being the path of length \(2n\) with periodic boundary conditions, is \[Z_{C_{2n},\boldsymbol{\lambda}}=\mathop{\mathrm{Tr}}(M^n).\] Write \(M=P^{-1}\Lambda P\) with \(\Lambda\) diagonal. Then the partition function of the cycle may be written as \[Z_{C_{2n},\boldsymbol{\lambda}}=\mathop{\mathrm{Tr}}(P^{-1}\Lambda^n P)=\mathop{\mathrm{Tr}}(\Lambda^n)=\alpha^n+\beta^n,\] where \(\alpha,\beta\) are the eigenvalues of \(\Lambda\). Note that to obtain a zero of the partition function we require \(|\alpha|=|\beta|\) and that \(|\arg(\alpha)-\arg(\beta)|\) divides \((2k+1)\pi\) for some \(k\in\mathbb{N}\).
For simplicity assume \(\mu=\bar\lambda\). The eigenvalues of \(M\) are \[\alpha,\beta=\frac{1}{2}\Big(\lambda+\mu+1\pm\sqrt{(\lambda+\mu+1)^2-4\lambda\mu}\Big)= \frac{1}{2}\Big(2\mathop{\mathrm{Re}}\nolimits\lambda+1\pm\sqrt{(2\mathop{\mathrm{Re}}\nolimits\lambda+1)^2-4|\lambda|^2}\Big).\] To ensure \(|\alpha|=|\beta|\), we insist that \[\label{eq:moduli} 4|\lambda|^2>(2\mathop{\mathrm{Re}}\nolimits\lambda+1)^2;\tag{3}\] and to ensure \(\alpha^n+\beta^n=0\) we take \[\label{eq:args} \arg\alpha=\pi/2n=-\arg\beta.\tag{4}\] Let \(\lambda=a+b\mathrm{i}\), so that \(\mu=a-b\mathrm{i}\). Then 3 simplifies to \[\label{eq:abcondition} 4b^2>4a+1,\tag{5}\] and 4 to \[\tan\Big(\frac{\pi{2n}}{\Big})=\frac{\sqrt{4b^2-4a-1}}{2a+1}\] or \[\label{eq:cycleroot} 4b^2=\Big((2a+1)\tan\Big(\frac{\pi{2n}}{\Big})\Big)^2+4a+1.\tag{6}\] Now, to find a pair of roots close to the parabola \(R(1)\) with a desired real part \(a\), simply fix \(a\) and take \(n\) large. As \(n\to\infty\), the imaginary part \(b\) tends to \(\sqrt{a+\frac{1}{4}}\) from above. ◻
Summarising, \(R(1)\) is a multivariate zero-free region for even length cycles, and is the unique maximal such region that is symmetric around the real axis in the following sense: for any point \(z\) on the boundary of \(R(1)\), and \(\varepsilon>0\), the set \(R(1)\cup B(z,\varepsilon)\cup B(\bar z,\varepsilon)\) is not multivariate zero free. Note that there is no reason a priori to suppose that a unique maximal zero-free region exists, and indeed we shall encounter counterexamples later.
5.2 Blow-ups of cycles (dense)↩︎
Here we generalise the previous example to graphs of higher degree (and larger cliques) to show that Theorem 6 gives a zero-free region that is not quite best possible, but close.
By \(C_{2n}[K_s]\) we denote the lexicographic product of a cycle of length \(2n\) and a clique of size \(s\geq2\). Thus, the vertex set of \(C_{2n}[K_s]\) is \([2n]\times[s]\) and each vertex subset \(\{i,i+1\}\times[s]\) (with artithmetic modulo \(2n\)) induces a \(2s\)-clique \(K_{2s}\). There are no further edges. It is easy to check that \(C_{2n}[K_s]\) is claw free; indeed, \(G[K_s]\) is claw free for any claw-free graph \(G\) and integer \(s\geq2\).
Although \(C_{2n}[K_s]\) is not a line graph (of a simple graph), it is the line graph of a multigraph and so is amenable to the method of Asano contractions (see Theorem 4 and appendix). As the cliques that comprise \(C_{2n}[K_s]\) have size \(2s\), this approach yields \(R(s^2)\) as a multivariate zero-free region. (Refer to Theorem 4.) Alternatively, since any maximum clique in \(C_{2n}[K_s]\) has size \(2s\) and is simplicial, our Theorem 6 yields \(R(2s)\) as a zero-free region. Below we see that Theorem 6 does not quite give the optimal zero-free region but comes close.
Lemma 7. \(R(s)\) is a multivariate zero-free region for the graph \(C_{2n}[K_s]\), for all \(s\geq2\). It is the maximal such region that is symmetric about the real axis.
Proof. Let \(\boldsymbol{\lambda}:[2n]\times[s]\to \mathbb{C}\) be a labelling of the vertices of \(C_{2n}[K_s]\). Define \(\boldsymbol{\lambda}':[2n]\to\mathbb{C}\) by \(\lambda'_i=\sum_{j\in[s]}\lambda_{ij}\), for \(i\in[2n]\). We view \(\boldsymbol{\lambda}'\) as a labelling of \(C_{2n}\). It is easy to verify that \(Z_{C_{2n}[K_s],\boldsymbol{\lambda}}=Z_{C_{2n},\boldsymbol{\lambda}'}\). (Regard two independent sets in \(C_{2n}[K_s]\) as equivalent if they intersect the same collection of sets of the form \(\{i\}\times[s]\); now collect together contributions to the partition function from equivalent independent sets.) Noting that \(R(1)\) is a zero-free region for \(C_{2n}\), we see that to establish the first part of the lemma it is enough to show that \(\lambda_{ij}\in R(s)\) for all \(j\in[s]\) implies \(\lambda'_i\in R(1)\).
Fix \(i\in[2n]\). Since \(\lambda_{ij}\in R(s)\) for all \(j\in[s]\) we have \[(\mathop{\mathrm{Im}}\nolimits\lambda_{ij})^2<\frac{1}{s}\mathop{\mathrm{Re}}\nolimits\lambda_{ij}+\frac{1}{4s^2},\quad\text{for all j\in[s]}.\] Summing over \(j\), \[\label{eq:R40141} \sum_{j\in[s]}(\mathop{\mathrm{Im}}\nolimits\lambda_{ij})^2<\frac{1}{s}\mathop{\mathrm{Re}}\nolimits\lambda'_{i}+\frac{1}{4s}.\tag{7}\] By Cauchy-Schwarz, \[(\mathop{\mathrm{Im}}\nolimits\lambda'_i)^2=\Bigg(\sum_{j\in[s]}1\cdot\mathop{\mathrm{Im}}\nolimits\lambda_{ij}\Bigg)^2\leq \sum_{j\in[s]}1^2\sum_{j\in[s]}(\mathop{\mathrm{Im}}\nolimits\lambda_{ij})^2=s\sum_{j\in[s]}(\mathop{\mathrm{Im}}\nolimits\lambda_{ij})^2.\] Combining this with 7 we see that \(\lambda'_i\in R(1)\).
Optimality of the zero-free region \(R(s)\) may be argued as follows. Suppose \(z_0\in\partial R(s)\) and \(\varepsilon>0\). Note that \(sz_0\in\partial R(1)\). By Lemma 6, there exist \(z\in B(sz_0,s\varepsilon)\) and \(\boldsymbol{\lambda}':[2n]\to\{z,\bar z\}\) such that \(Z_{C_{2n},\boldsymbol{\lambda}'}=0\). Now let \(\boldsymbol{\lambda}=\boldsymbol{\lambda}'/s\). Then \(z/s\in B(z_0,\varepsilon)\), \(\boldsymbol{\lambda}:[2n]\to\{z/s,\bar z/s\}\) and \(Z_{C_{2n}[K_s],\boldsymbol{\lambda}} =Z_{C_{2n},\boldsymbol{\lambda}'}=0\). ◻
5.3 Paths with longer range interactions↩︎
The following are examples of graphs in \(\mathcal{G}^{\mathrm{Cl-S}}\) that are not line graphs thus showing that Theorem 6 applies to graphs that Theorem 4 does not apply to.
For \(n,d\geq1\), let \(P_n^{(d)}\) denote the path of length \(n\) with adjacencies up to distance \(d\). So \(V(P_n^{(d)})=[n]\) and \(E(P_n^{(d)})=\{ij:i,j\in[n]\text{ and }1\leq j-i\leq d\}\). Assume that \(d\geq2\). Then for \(n\) sufficiently large, the graph \(P_n^{(d)}\) is not the line graph of a multigraph. (As the property is hereditary, we can take \(n=3d\) without loss of generality. Any line graph can be covered by cliques in such a way that each vertex is in at most two cliques. Assume that the edges of \(P_{3d}^{(d)}\) could be covered by such cliques. In particular, the edge \(\{d,2d\}\) must be in some such clique \(K\). The vertex \(d\) has degree \(2d\), so to cover all its incident edges using two cliques requires \(K\) to be of maximum cardinality, i.e., \(K=\{d,d+1,\ldots,2d\}\). This in turn forces us to take the cliques \(\{0,\ldots,d\}\), \(\{d,\ldots,2d\}\) and \(\{2d,\ldots,3d\}\). But now it is impossible to cover (say) the edges \(\{1,d+1\}\) and \(\{d+1,2d+1\}\) using a single extra clique.) Thus, this example is not amenable to the Asano contraction approach.
However, \(P_n^{(d)}\) is claw free and has a simplicial clique, for example, the singleton vertex \(\{0\}\). Its maximum clique size is \(d+1\), so by Theorem 6 it has \(R(d+1)\) as a multivariate zero-free region.
5.4 Blow-ups of cycles (sparse)↩︎
By \(C_{2n}[sK_1]\) we denote the lexicographic product of a cycle of length \(2n\) and an independent set of size \(s\geq2\). Thus, the vertex set of \(C_{2n}[sK_1]\) is \([2n]\times[s]\) and each pair of vertex subsets \(\{i\}\times[s]\) and \(\{i+1\}\times[s]\) (with arithmetic modulo \(2n\)) induces a complete bipartite graph \(K_{s,s}\). There are no further edges. It is easy to check that \(C_{2n}[sK_1]\) is E-free (and hence \(S_{i,j,k}\)-free for \(i \geq 1\) and \(j,k \geq 2\)); indeed, for any E-free graph \(G\) and integer \(s\geq2\), the graph \(G[sK_1]\) is also E-free
Since \(C_{2n}[2K_1]\) is E-free, we deduce from Theorem 5 the existence of an open multivariate zero-free region containing any finite segment of the positive real axis. We cannot, however, deduce the existence of an open zero-free region containing the entire real axis. In fact, we now show that no such region exists.
Lemma 8. Consider the collection \(\mathcal{C}=\{C_{2n}[2K_1]:n\in\mathbb{N}\}\) of blown-up cycles defined above. There is no open multivariate zero-free region for \(\mathcal{C}\) that contains the entire real axis.
Proof. Suppose \(\varepsilon>0\). Define a weighting \(\boldsymbol{\lambda}^\varepsilon:[2n]\times[2]\to\mathbb{C}\) of the vertices of \(C_{2n}[2K_1]\) by \[\lambda_{ij}^\varepsilon=\begin{cases} W,&\text{if j=0;}\\ w_\varepsilon=1+\varepsilon\mathrm{i},&\text{if i is even and j=1};\\ \bar{w_\varepsilon}=1-\varepsilon\mathrm{i},&\text{if i is odd and j=1}, \end{cases}\] where \(W\in\mathbb{R}\) and \(\varepsilon>0\) will be chosen presently. As before, by grouping equivalent independent sets, we can write down an equivalent (in the sense of preserving the partition function) weighting \(\boldsymbol{\mu}^\varepsilon\) of the simple cycle \(C_{2n}\): \[\mu^\varepsilon_i=\begin{cases} z_\varepsilon:= (W+1)(w_\varepsilon+1)-1=(2W+1)+(W+1)\varepsilon\mathrm{i},&\text{if i is even;}\\ \bar{z_\varepsilon} := (W+1)(\bar{w_\varepsilon}+1)-1=(2W+1)-(W+1)\varepsilon\mathrm{i},&\text{if i is odd.} \end{cases}\] We then have \(Z_{C_{2n}[2K_1],\boldsymbol{\lambda}^\varepsilon}=Z_{C_{2n},\boldsymbol{\mu}^\varepsilon}\).
With a view to obtaining a contradiction, assume that \(S\) is an open multivariate zero-free region containing the positive real axis. Choose \(\varepsilon>0\) such that the interval \([1+\varepsilon\mathrm{i},1-\varepsilon\mathrm{i}]\) is contained in \(S\). Then choose \(W\) so that \(\varepsilon^2(W+1)>2\). With these choices, \(z_\varepsilon\) and \(\bar{z_\varepsilon}\) lie outside the parabola \(R(1)\), i.e., outside the zero-free region for simple cycles. There are just a countable set of choices for the cycle \(C_{2n}\), so we cannot expect \(Z_{C_{2n},\boldsymbol{\mu}^\varepsilon}\) to be zero for any weighting exactly of the form \(\boldsymbol{\mu}^\varepsilon:[2n]\to\{z_\varepsilon,\bar z_\varepsilon\}\). However, we can find a nearby zero. As in the proof of Lemma 6, we can choose \(\delta\in(0,\varepsilon)\) such that \(\delta^2(W+1)>2\) continues to hold, and such that there exist \(n\in\mathbb{N}\) and \(\boldsymbol{\mu}^\delta:[2n]\to\{z_\delta,\bar{z_\delta}\}\) such that \(Z_{C_{2n},\boldsymbol{\mu}^\delta}=0\). As we noted earlier, this implies \(Z_{C_{2n}[2K_1],\boldsymbol{\lambda}^\delta}=0\), contradicting the assumption that \(S\) is zero free. ◻
5.5 Complete multipartite graphs↩︎
In this subsection, we show that we cannot drop the bounded degree condition in Theorem 3 and Theorem 5. For \(a,b,n,m \in \mathbb{N}\), let \(K(a,b;n,m)\) be the graph that has \(an + bm\) vertices which are divided into \(a\) sets with \(n\) vertices and a further \(b\) sets of \(m\) vertices and where all edges are present between vertices in different sets and no edges are present inside any of the sets. So this is a complete multipartite graph. Note that \(K(a,b;n,m)\) is \(S_{i,j,k}\)-free for any choice of positive integers \(i,j,k\) except for \(i=j=k=1\), i.e., the graph may contain claws but does not contain any other subdivided claw.
One can easily verify that the (univariate) independence polynomial of \(K(a,b; n,m)\) is given by \[Z_{K(a,b;n,m), \lambda} = a[(1+\lambda)^n - 1] + b[(1+ \lambda)^m - 1)] + 1 = a(1+\lambda)^n + b(1+\lambda)^m + (1-a-b).\] From the following lemma, it immediately follows that the roots of such polynomials are dense in the complex plane except possibly inside a disc of radius \(1\) centered at \(-1\). This shows in particular that zeros accumulate on the positive real line and so we cannot expect a zero-free region around the positive real line (or any section of it) for the general class of \(S_{i,j,k}\)-free graphs where \(i,j \geq 1\) and \(k \geq 2\).
Lemma 9. For the set of polynomials of the form \(ax^{2n} + bx^n + (1-a-b)\), where \(a,b,n \in \mathbb{N}\), the roots are dense outside the unit disc.
Note that there are zeros inside the unit disc, but we do not describe them here.
Proof. First consider quadratics of the form \(ax^2 + bx + (1-a-b)\), where \(a\) and \(b\) are positive integers. We claim that the roots of such quadratics are dense in the interval \((-\infty, -1)\). Indeed, given any positive rational \(t\), we can find a root arbitrarily close to \(-1-t\) as follows. Take \(L\) to be a very large positive integer so that \(b=tL\) is an integer and set \(a=L\). Then one of the roots of \(ax^2 + bx + (1-a-b)\) is \[\begin{align} -\frac{b}{2a} - \frac{(b^2 - 4a(1-a-b))^{1/2}}{2a} = -\frac{t}{2} - \left( \left( \frac{t}{2}+1 \right)^2 - \frac{1}{L} \right)^{1/2} = -t-1 + O(L^{-1}). \end{align}\] proving the claim.
Next, given any \(z = re^{\mathrm{i}\theta}\) with \(r>1\) and \(\varepsilon > 0\), consider a small neighbourhood of \(z\) given by \[N_{\varepsilon}(z) = \{r'e^{\mathrm{i}\theta'} : |r-r'| \leq \varepsilon, |\theta - \theta'| \leq \varepsilon/r \},\] which is easily checked to be contained inside a disc of radius \(3 \varepsilon\) centered at \(z\). For a sufficiently large positive integer \(N\) (we can take \(N \geq \pi r\varepsilon^{-1}\) ), the set \(N_{\varepsilon}(z)^N\) (raising each element in \(N_{\varepsilon}(z)\) to the power \(N\)) is an annulus between the circles of radius \((r-\varepsilon)^N\) and \((r+\varepsilon)^N\) and in particular crosses the interval \((-\infty, -1)\) and so contains a root of \(Ax^2 + Bx + (1-A-B)\) for some positive integers \(A,B\). Therefore, some complex number within a distance \(3\varepsilon\) of \(z\) is a root of \(Ax^{2N} + Bx^N + (1 -A - B)\). ◻
6 The case when \(H\) is neither a subdivided claw nor a path↩︎
Recall that Theorem 3 and Theorem 5 give a zero-free region for the independence polynomials of \(H\)-free graphs of fixed maximum degree \(\Delta\), where \(H\) is a fixed subdivided claw \(S_{i,j,k}\). Note that similar results hold when \(H = P_k\) is a path of some fixed length \(k\) for the trivial reason that there are only finitely many \(P_k\)-free graphs of maximum degree \(\Delta\). In this section, we show that no similar results can hold for any graph \(H\) that is not a subdivided claw or a path.
Given a graph \(H\) which is neither a path nor a subdivided claw, then either \(H\) has a vertex of degree at least \(4\) or \(H\) has (at least) two vertices of degree \(3\). In the latter case, set \(k\in\mathbb{N}\) to be larger than the distance between these vertices of degree \(3\) and and in the former case, set \(k=0\). Let \(\mathcal{T}=\{T_d:d\in\mathbb{N}\}\) be the family of trees, where \(T_d\) is obtained from the complete binary tree of height \(d\) by subdividing each edge \(2k\) times (so there are \(2k\) intermediate vertices between branch vertices). Refer to Figure 3. By our choice of \(k\), all trees in \(\mathcal{T}\) are \(H\)-free.
Lemma 10. The set of zeros \[\big\{\lambda\in\mathbb{C}: Z_{T,\lambda}=0\text{ for some }T\in\mathcal{T}\big\}\] has an accumulation point on the positive real axis.
The lemma shows that, for any choice of \(H\) that is not a subdivided claw or a path, there can be no zero-free region containing the positive real line for independence polynomials of \(H\)-free graphs of maximum degree \(3\). Our proof closely follows the treatment of Buys [30] and so we give details where our proof differs from [30] and only outline the rest.
Proof of Lemma 10. The advantage of working with trees is that we have an inductive description of the partition function. A particularly convenient way of managing the calculation is through the occupation ratio of the root of a tree: the total weight of independent sets that include the root vertex divided by the total weight of independent sets that exclude it. The recurrence for the occupation ratio was introduced into this area by Weitz [33], and can be found in earlier work, such as Kelly [34]. The derivation of the recurrence can be found in Buys [30]. Define \[f_{\lambda,1}(z)=\frac{\lambda{1+z}}{,}\> f_{\lambda,2}(z)=\frac{\lambda{(1+z)^2}}{\>}\text{ and }\> g_\lambda(z)=f_{\lambda,2}\circ f_{\lambda,1}^{\circ 2k}(z)=f_{\lambda,2}\circ \underbrace{f_{\lambda,1}\circ\cdots\circ f_{\lambda,1}}_\text{2k copies}(z).\] The functions \(f_{\lambda,1}\) and \(f_{\lambda,2}\) express how the occupation ratio is transformed as we go one level up in the tree; \(f_{\lambda,1}\) (respectively, \(f_{\lambda,2}\)) relates to vertices with branching factor 1 (respectively, 2). Refer to Figure 3. It follows that \(g_\lambda^{\circ d}(\lambda)\) is the occupation ratio of the root of \(T_d\). If \(g_\lambda^{\circ d}(\lambda)=-1\) then the contributions from independent sets that include the root and those that exclude it exactly cancel out and we have \(Z_{T_d,\lambda}=0\). Following Buys, our initial goal is to find a fugacity \(\lambda_0\in\mathbb{R}_{>0}\) such that \(g_{\lambda_0}\) has an indifferent fixed point \(z_{\lambda_0}\), that is to say \(g_{\lambda_0}(z_{\lambda_0})=z_{\lambda_0}\) and \(|g'_{\lambda_0}(z_{\lambda_0})|=1\).
Fix \(\lambda\in\mathbb{R}_{>0}\). Observe that \(f_{\lambda,1}\) and \(f_{\lambda,2}\) are monotonically decreasing as functions on \(\mathbb{R}_{\geq0}\), and hence so is \(g_\lambda\), being a composition of an odd number of these. As \(g_\lambda\) is also non-negative on \(\mathbb{R}_{\geq0}\) it intersects the identity function at a unique point in \(\mathbb{R}_{\geq0}\); call this point \(z_\lambda\). Since \(g_0\) is identically zero, we have \(z_0=0\) and \(|g'_0(z_0)|=0\) . We will show that \(|g'_\lambda(z_\lambda)|\to2\) as \(\lambda\to\infty\) from which it follows, by continuity,3 that there exists at least one \(\lambda\in\mathbb{R}_{>0}\) at which \(|g'_\lambda(z_\lambda)|=1\). This will give us the sought for indifferent fixed point.
As \(k\) is constant, and we are taking \(\lambda\) to be sufficiently large, we can approximate the occupation ratio of the root of \(T_1\) — with the two leaves weighted \(z\), and the remaining vertices weighted \(\lambda\) — by enumerating just the maximum independent sets. Then the occupation ratio of the root is \(g_\lambda(z)=w_\mathrm{in}/w_\mathrm{out}\), where \[\begin{align} w_\mathrm{in}&=\big(\lambda^{2k+1}+O(\lambda^{2k})\big)+2z\big(k\lambda^{2k}+O(\lambda^{2k-1})\big)+z^2\big(k^2\lambda^{2k-1}+O(\lambda^{2k-2})\big)\\ &=\lambda^{2k-1}(\lambda+kz)^2(1+ O(\lambda^{-1})),\\ \noalign{\noindent and} w_\mathrm{out}&=\big((k+1)^2\lambda^{2k}+O(\lambda^{2k-1})\big)+2z\big((k+1)\lambda^{2k}+O(\lambda^{2k-1})\big)+z^2\big(\lambda^{2k}+O(\lambda^{2k-1})\big)\\ &=\lambda^{2k}(z+k+1)^2(1+ O(\lambda^{-1})). \end{align}\] Thus \[g_\lambda(z)=\frac{(\lambda+kz)^2}{\lambda(z+k+1)^2}(1\pm O(\lambda^{-1})).\] At a fixed point, \(g_\lambda(z)=z\) and \(z=(1\pm o(1))\lambda^{1/3}\). Letting \(\sim\) denote equality up to a factor \((1\pm o_\lambda(1))\), and \(z=z_{\lambda}\) the identified fixed point, we have \(z_{\lambda}\sim\lambda^{1/3}\). Also, \[f_{\lambda,1}^{\circ \ell}(z_\lambda)\sim\begin{cases} \lambda^{1/3},&\text{if \ell is even;}\\ \lambda^{2/3},&\text{if \ell is odd.} \end{cases}\] By the chain rule, \[g'_\lambda(z) =(f'_{\lambda,2}\circ f_{\lambda,1}^{\circ 2k}(z)) \times (f'_{\lambda,1}\circ f_{\lambda,1}^{\circ (2k-1)}(z)) \times \cdots \times (f'_{\lambda,1}\circ f_{\lambda,1}(z)) \times f'_{\lambda,1}(z).\] Noting \[f'_{\lambda,1}(z)=\frac{-\lambda}{(1+z)^2}\> \text{ and }\> f'_{\lambda,2}(z)=\frac{-2\lambda}{(1+z)^3},\] we have \[g'_\lambda(z_\lambda)\sim-2 \times \underbrace{(-\lambda^{-1/3} \times -\lambda^{1/3})\times\cdots\times (-\lambda^{-1/3} \times -\lambda^{1/3})}_{\text{k factors}}=-2.\] By continuity, there exists \(\lambda\in\mathbb{R}_{>0}\) such that \(|g'_\lambda(z_\lambda)|=1\). Let this \(\lambda\) be \(\lambda_0\). Then \(z_{\lambda_0}\) is an indifferent fixed point of \(g_{\lambda_0}\).
We now employ [30]. In our application, \(\Delta=2\), and \(H_\Delta=H_2\) is the set of all functions that can be obtained by composing sequences composed of \(f_{\lambda,1}\) and \(f_{\lambda,2}\). The lemma asserts that the existence of an indifferent fixed point at \(\lambda=\lambda_0\) (just established) ensures that \(\lambda_0\) is an accumulation point of zeros realised by balanced trees with branching factors in \(\{1,2\}\). In our application, however, we want to ensure that pairs of degree-2 vertices remain separated, by \(2k\) degree-1 vertices. In fact, the trees \(T\in H_2\) referred to in the statement of Buys’ Lemma 13 do have this property. However, we have to peek into the proof to see this.
The proof of the lemma first establishes that a certain function \(g_\lambda^{\circ n}\circ h_\lambda\) is not ‘normal’ about \(\lambda=\lambda_0\). The function \(g_\lambda\) and the point \(\lambda_0\) are the same as ours, so the issue for us is whether the \(h_\lambda\in H_2\) has two occurrences of \(f_{\lambda,2}\) that are too close together. Consulting Remark 8, we discover that \(h_\lambda\) is in fact an initial segment of the composition \(f_{\lambda,2}\circ f_{\lambda,1}^{\circ 2k}\), so in fact contains at most one occurrence of \(f_{\lambda,2}\). Finally, at the end of the proof of Lemma 13, either one or two functions are removed from the composition of functions \(g_\lambda^{\circ n}\circ h_\lambda\) to yield the desired function \(\tilde{g}_\lambda\). Thus, \(\tilde{g}_\lambda\) is a composition of a contiguous subsequence of functions from \[g_{\lambda}^{\circ(n+1)}=(f_{\lambda,2}\circ f_{\lambda,1}\circ\cdots\circ f_{\lambda,1})\circ (f_{\lambda,2}\circ f_{\lambda,1}\circ\cdots\circ f_{\lambda,1})\circ\cdots\circ(f_{\lambda,2}\circ f_{\lambda,1}\circ\cdots\circ f_{\lambda,1}).\] The corresponding tree has pairs of degree-2 vertices separated by sequences of \(2k\) degree-1 vertices, as desired. ◻
7 Concluding Remarks↩︎
A few natural questions arise from this work. First, in Theorem 3, we establish an open, zero-free region \(F\) containing \([0, \infty)\) for \(S_{t,t,t}\)-free graphs of maximum degree \(\Delta\). Can we in fact take \(F\) to be a sector of the complex plane with a suitably small angle (depending on \(\Delta\) and \(t\))?
Secondly, it would be interesting to know whether some form of Theorem 6 can be extended to all claw-free graphs of bounded degree (or bounded clique size). A more basic question is whether there is an open multivariate zero-free region containing \([0, \infty)\) for claw-free graphs of bounded degree (or bounded clique size).
Acknowledgments↩︎
We thank Guus Regts and Ferenc Bencs for helpful discussions and feedback on an earlier draft.
8 Appendix↩︎
The line graph of a multigraph may be characterised as a graph \(G\) for which there exist vertex subsets \(V_1,V_2,\ldots V_\ell\subseteq V(G)\) with the following properties: (i) every induced graph \(G[V_i]\) is a clique; (ii) every edge \(e\in E(G)\) is contained in some clique \(G[V_i]\); and (iii) every vertex \(v\in V(G)\) is contained in at most two cliques.
Proof of Theorem 4. Suppose \(G\) is a line graph of a multigraph, whose maximum clique in the above decomposition has size \(k_0\). We show that \(R(k_0^2/4)\) is a multivariate zero-free region for \(G\). Note that \(k_0\) is at most the size of the largest clique in \(G\), so this shows a little more than claimed in Theorem 4.
We use the technique of Asano contractions, as employed in this context by Lebowitz, Ruelle and Speer. The proof of our claim is essentially contained in the terse proof of their Lemma 2.6 [7]. Here, we sketch the line of proof, specialise it to our specific application, and explicitly compute the parabolic region.
The independence polynomial of the clique \(K_k\) is simply \(z_1+z_2+\cdots z_k+1\), and has \(\{z:\mathop{\mathrm{Re}}\nolimits z>-k^{-1}\}\) as a multivariate zero-free region. View the line graph \(G\) as being constructed from a set of disjoint cliques by sequentially identifying pairs of vertices. Each clique individually has the halfspace \(\Phi=\{z:\mathop{\mathrm{Re}}\nolimits z>-k_0^{-1}\}\) as a multivariate zero-free region. Clearly, the disjoint union of cliques \(G_0=G[V_1]\mathbin{\mathaccent\cdot\cup}G[V_2]\mathbin{\mathaccent\cdot\cup}\cdots\mathbin{\mathaccent\cdot\cup}G[V_\ell]\) also has \(\Phi\) as a multivariate zero-free region. A halfspace is a special case of a “circular region”, so Asano contraction is applicable.
Let the independence polynomial of \(G_0\) be \(p(z_1,\ldots,z_N)\). Think of the zero-free region as being the cartesian product \(\Phi_1\times\Phi_2\times\cdot\times\Phi_N\), where, initially, \(\Phi_i=\Phi\) for all \(i\). If \(z_i\in\Phi_i\) for all \(i\) then \(p(z_1,\ldots,z_N)\not=0\). We can recover \(G\) from \(G_0\) by repeatedly identifying pairs of vertices. Suppose, without loss of generality, that we identify the vertices labelled by \(z_{N-1}\) and \(z_N\) first, and assign variable \(z\) to the coalesced vertex. The key contraction lemma (see [7]) says that the resulting independence polynomial, in variables \((z_1,\ldots,z_{N-2},z)\), has a zero-free region \(\Phi_1\times\Phi_2\times\cdot\times\Phi_{N-2}\times\Phi'\), where \(\Phi_1,\Phi_2\ldots,\Phi_{N-2}=\Phi\) and \(\Phi'\) is obtained from \(\Phi_{N-1}\) and \(\Phi_N\) according to a certain rule, namely \[\begin{align} \Phi'=\overline{-\overline{\Phi_{N-1}}\cdot\overline{\Phi_N}}&=\overline{\{-w_1w_2:\text{w_1\notin\Phi_{N-1} and w_2\notin\Phi_N}\}}\\&=\overline{\{-w_1w_2:\mathop{\mathrm{Re}}\nolimits w_1,\mathop{\mathrm{Re}}\nolimits w_2\leq-k_0^{-1}\}}, \end{align}\] where overline denotes complement of a set.
Then, repeatedly applying Asano contractions we reach the target graph \(G\), and discover that it has \((\Phi')^n\) as a zero free set, where \(n=|V(G)|\). (It is here that we crucially use the fact that the original graph \(G\) is a line graph. As each vertex is contained in at most two cliques, we are always replacing two zero-free sets \(\Phi\) by a single \(\Phi'\). If \(G\) is the line graph of a multigraph, then \(G\) may contain parallel edges, but this is fortunately not an issue for the hard-core model.)
It only remains to show that \(\Phi'=R(k_0^2/4)\). The set \(\Phi'\) is open and we want to identify its boundary \(\partial\Phi'\). If either \(\mathop{\mathrm{Re}}\nolimits w_1<-k_0^{-1}\) or \(\mathop{\mathrm{Re}}\nolimits w_2<-k_0^{-1}\) then by making small perturbations of \(w_1\) or \(w_2\) (note that neither is zero) within \(\overline{\Phi}\) we can move in a small open region around \(w_1w_2\). So, the boundary of \(\Phi'\) must be defined by \(w_1, w_2\) lying on the boundary of \(\Phi\). Let \(w_1=-k_0^{-1}+y_1\mathrm{i}\) and \(w_2=-k_0^{-1}+y_2\mathrm{i}\), with \(y_1,y_2\in\mathbb{R}\). Then \[-w_1w_2=f(y_1,y_2)=(y_1y_2-k_0^{-2})+k_0^{-1}(y_1+y_2)\,\mathrm{i}.\] Now, \(\partial f/\partial y_1= y_2+k_0^{-1}\mathrm{i}\) and \(\partial f/\partial y_2= y_1+k_0^{-1}\mathrm{i}\), so unless \(y_1=y_2\) we can again move in an open set around \(f(y_1,y_2)\), and hence \(f(y_1,y_2)\) cannot be on the boundary of \(\Phi'\). Setting \(y=y_1=y_2\) we obtain the parametric expression \((y^2-k_0^{-2})+2k_0^{-1}y\,\mathrm{i}\) for the boundary of \(R(k_0^2/4)\) and hence \(\Phi' = R(k_0^2/4)\). ◻
References↩︎
As Theorem 4 is only implicit in [7], we provide some details of the proof, including an explicit description and derivation of the zero-free set, in the Appendix (Section 8).↩︎
Note that \(U \setminus \partial L\) must be a strict subset of \(V\) since either \(U\) is a strict subset of \(V\) or \((L,U)=(\emptyset,V)\) (from earlier) in which case \(\partial L =\{u\}\).↩︎
The fixed point \(z=z_\lambda\) is defined by the implicit equation \(t(\lambda,z)=0\), where \(t(\lambda,z)=g_\lambda(z)-z\). Note that \(\frac{\partial t}{\partial z}\) is at most \(-1\) and, in particular is non-zero. Now apply the implicit function theorem.↩︎