Proof. Recall that

\[ \mathcal{R}_\Delta^i \;:\!=\; \{R_{G,v}\;:\;(G,v) \in \mathcal{G}_\Delta^i\} \]

and thus $\mathcal{R}_\Delta^1 \subseteq \mathcal{R}_\Delta^{\Delta-1}$ . It follows that if $\mathcal{R}_\Delta^{\Delta-1}$ is normal at $\lambda_0$ then the same holds for $\mathcal{R}_\Delta^{1}$ .

To show the other direction, assume that $\mathcal{R}_\Delta^{1}$ is normal at $\lambda_0$ . Note that the family $\mathcal{R}_\Delta^\Delta$ is normal at 0 by Lemma 2·10, hence we can assume $\lambda_0 \neq 0$ . As $\mathcal{R}_\Delta^{1}$ is normal at $\lambda_0$ , there is a neighbourhood U of $\lambda_0$ on which $\mathcal{R}_\Delta^{1}$ is a normal family. We can take U such that $0 \not \in U$ . We will show that $\mathcal{R}_\Delta^{\Delta-1}$ is also a normal family on U. To that effect take a sequence of rooted graphs $\{(G_n,v_n)\}_{n \geq 1} \subseteq \mathcal{G}_\Delta^{\Delta-1}$ . Construct the rooted graphs $(\hat{G}_n, \hat{v}_n) \in \mathcal{G}_\Delta^1$ by attaching a root $\hat{v}_n$ to the root $v_n$ of $G_n$ by a single edge. By assumption the sequence $\{R_{\hat{G}_n,\hat{v}_n}\}_{n \geq 1}$ has a subsequence that converges locally uniformly to a function $H\;:\;U \to \widehat{\mathbb{C}}$ . Let $I \subseteq \mathbb{N}$ be the indices belonging to this subsequence. By Lemma 2·6 we have $R_{\hat{G}_n,\hat{v}_n}(\lambda) = f_\lambda(R_{G_n,v_n}(\lambda))$ for every $\lambda \in U$ . Because U does not contain 0, the Möbius transformation $f_\lambda$ is invertible for every $\lambda\in U$ . Therefore for these $\lambda$ we have

\[ \lim_{\substack{n \to \infty\\[5pt] n \in I}} R_{G_n,v_n}(\lambda) = \lim_{\substack{n \to \infty\\[5pt] n \in I}} f_\lambda^{-1}(f_\lambda(R_{G_n,v_n}(\lambda))) = \lim_{\substack{n \to \infty\\[5pt] n \in I}} f_\lambda^{-1}(R_{\hat{G}_n,\hat{v}_n}(\lambda)) = f_\lambda^{-1}(H(\lambda)). \]

Because the map $U \times \widehat{\mathbb{C}} \to \widehat{\mathbb{C}}$ that sends $(\lambda,z)$ to $f_\lambda^{-1}(z)$ is continuous, we can conclude that this limit converges locally uniformly on U. Therefore we have shown that the sequence $\{R_{G_n,v_n}\}_{n \geq 1}$ has a subsequence that converges locally uniformly to the holomorphic function $\lambda \mapsto f_\lambda^{-1}(H(\lambda))$ , and thus $\mathcal{R}_\Delta^{\Delta-1}$ is normal at $\lambda_0$ .

Proof. Let us assume $\lambda \in \overline{\mathcal{Z}_\Delta}$ . Then for any open neighbourhood V of $\lambda$ there is a $\lambda_0 \in V$ for which $Z_G(\lambda_0) = 0$ for some $G \in \mathcal{G}_\Delta$ . We will prove that the family $\mathcal{R}_\Delta^{\Delta-1}$ cannot be normal on V.

By Lemma 2·3 there is a a rooted tree $(T,u) \in \mathcal{G}_\Delta^1$ for which $R_{T,u}(\lambda_0) = -1$ . Consider the rooted trees $(T_n,v)$ obtained by implementing a copy of (T, u) in every vertex of the rooted paths $(P_n, v)$ . It follows from Lemma 2·8 that

\begin{align*}R_{T_n, v} = R_{P_n,v} \circ R_{T,u}.\end{align*}

We note that in $T_n$ the root v has degree $2 \leq \Delta - 1$ . Furthermore $R_{T,u}$ maps a neighbourhood of $\lambda_0$ holomorphically to a neighbourhood of $-1$ , since $R_{T,u}$ is not constantly equal to $-1$ . Lemma 3·4 states that the family $\{R_{P_n, v}\}_{n > 0}$ is not normal at $-1$ and thus it follows that $\{R_{T_n,v}\}_{n > 0}$ is not normal at $\lambda_0$ .

Proof. It follows from the conclusion of Section 4, i.e. $\mathcal{A}_\Delta = \overline{\mathcal{Z}_\Delta}$ , that $Z_G(\lambda) \neq 0$ for all $\lambda \in U$ and $G \in \mathcal{G}_\Delta$ . Suppose $\{R_{G_n,v_n}\}_{n\geq 1}$ does not converge to $-1$ locally uniformly on U. Then, after taking a subsequence if necessary, we may assume that $\{R_{G_n,v_n}\}_{n\geq 1}$ converges locally uniformly on U to a non-constant holomorphic function f. Clearly $f(\lambda_0)=-1$ . Since zeros of holomorphic functions are isolated there exists $\varepsilon>0$ so that $\overline{B(\lambda_0,\varepsilon)}\subset U$ and such that

\begin{align*}\delta \;:\!=\; \inf_{\lambda\in\partial B(\lambda_0,\varepsilon)}|f(\lambda)+1|>0.\end{align*}

Let n be sufficiently large so that $|R_{G_n,v_n}-f|<\delta$ uniformly on $\overline{B(\lambda_0,\varepsilon)}$ . Then

\[|(R_{G_n,v_n}(\lambda)+1)-(f(\lambda)+1)|<\delta< |f(\lambda)+1| + |R_{G_n,v_n}(\lambda)+1|\]

for all $\lambda \in \partial B(\lambda_0,\varepsilon)$ . There exists $\lambda_1\in B(\lambda_0,\varepsilon)$ for which $R_{G_n,v_n}(\lambda_1)=-1$ by Rouché’s theorem. By Lemma 2·1 it follows $\lambda_1$ is a zero of the independence polynomial $Z_{G}$ for some graph G of maximum degree at most $\Delta$ , which is a contradiction as we assumed $\lambda_0 \in \mathbb C \setminus \mathcal{A}_\Delta = \mathbb C \setminus \overline{\mathcal{Z}_\Delta}$ .

Proof. If this is not the case then, as in the previous lemma, we may assume that $\{R_{G_n,v_n}\}_{n\geq 1}$ converges locally uniformly to a non-constant holomorphic function f with $f(\lambda_0)=\mu$ . By Rouché’s theorem we can find $\lambda_1\in U$ and n sufficiently large so that $R_{G_n,v_n}(\lambda_1)=\mu$ , by the same argument as in the previous lemma.

Consider the family of rooted graphs $\{(\widetilde{G}_k,w_k)\}$ obtained by implementing $(G_n,v_n)$ in every vertex of the rooted paths $(P_{k},w_k)$ , where $P_k$ is the path with k vertices and $w_k$ is one of its extreme vertices. Since $v_n$ has degree 1, the graph $\widetilde{G}_k$ has maximum degree at most $\Delta$ . Hence by Lemma 2·6 we have

\begin{align*}R_{\widetilde{G}_k,w_k}(\lambda)=f^{k}_{R_{G_n,v_n}(\lambda)}(0).\end{align*}

By Lemma 3·4 the family $\{R_{P_k,w_k}\}=\{\lambda\mapsto f^k_{\lambda}(0)\}$ is non-normal at $\lambda=\mu$ , and therefore the family $\{R_{\widetilde{G}_k,w_k}\}$ is non-normal at $\lambda_1$ , contradicting the fact that the family $\mathcal{R}_\Delta$ is normal on U.

Proof. If $\mu=-1$ the result follows by Lemma 5·3. We may therefore assume that $\mu\neq -1$ . Recall that we denote $f_\lambda(z)=\lambda/(1+z)$ . We will show for each $\mu \in \mathbb{R}$ there exists $\mu_1, \mu_2, \mu_3 \le -{1}/{4}$ so that

\begin{align*}f_{\mu_m}\circ\cdots\circ f_{\mu_1}(\mu)=-1,\end{align*}

for some $m \leq 3$ . We distinguish between different cases:

1. (i) $\mu\ge -3/4$ . Take $\mu_1=-1-\mu\le -1/4$ , one can check $f_{\mu_1}(\mu)=-1$ ;

2. (ii) $\mu<-1$ . Take $\mu_1=-1/4$ and $\mu_2 = 1 - f_{\mu_1}(\mu)$ , then $f_{\mu_1}(\mu)>0>-3/4$ and so $\mu_2 \leq -1/4$ . One can check $f_{\mu_2} \circ f_{\mu_1} (\mu) = -1$ ;

3. (iii) $-1<\mu<-3/4$ . Take $\mu_1= \mu_2 = -1/4$ and $\mu_3 = 1 - f_{\mu_2}(f_{\mu_1}(\mu))$ , then $f_{\mu_1}(\mu)<-1$ so we see $\mu_3 \leq -1/4$ . One can check $f_{\mu_3} \circ f_{\mu_2} \circ f_{\mu_1} (\mu) = -1$ .

We may assume that $\{R_{G_n,v_n}\}_{n\geq 1}$ converges locally uniformly on U to a holomorphic function f with $f(\lambda_0)=\mu$ . We want to show f is constant on U. Since the set $\{R_{G,v}(\lambda_0)\;:\;(G,v) \in \mathcal{G}_\Delta^1\}$ is dense in $\hat{\mathbb{C}}$ by assumption, we can choose sequences of rooted graphs $\{(G_n^i,v_n^i)\}_{n \geq 1}$ in $\mathcal{G}_\Delta^1$ so that $\{R_{G_n^i,v_n^i}(\lambda_0)\}_{n\geq 1}$ converges to $\mu_i$ for each $i=1,\ldots,m$ . By Lemma 5·4 every sequence $\{R_{G_n^i,v_n^i}\}_{n\geq 1}$ converges locally uniformly on U to the constant function $\mu_i$ for each i.

Consider for each $n\geq 1$ , the rooted graph $(\widetilde G_n,v_n^m)$ obtained by implementing the rooted graphs $(G_n,v_n)$ , $(G_n^1,v_n^1),\ldots, (G_n^m,v_n^m)$ on the vertices of the path $P_{m+1}$ of length m. Note that $\widetilde G_n$ has maximum degree at most $\Delta$ .

It follows from Lemma 2·6 that

\[R_{\widetilde G_n,v^m_n}(\lambda) = f_{R_{G_n^m,v^m_n}(\lambda)}\circ \cdots \circ f_{R_{G_n^1,v^1_n}(\lambda)}\circ R_{G_n,v_n}(\lambda).\]

By our choice of the $\mu_i$ the sequence of ratios $\{R_{\widetilde G_n,v^m_n}(\lambda_0)\}_{n\geq 1}$ converges to $f_{\mu_m}\circ\cdots\circ f_{\mu_1}(\mu)=-1$ . Hence by Lemma 5·3 the sequence of ratios $\{R_{\widetilde G_n,v^m_n}\}_{n\geq 1}$ converges locally uniformly to the constant function $-1$ . Furthermore the sequence of ratios $\{R_{\widetilde G_n,v^m_n}\}_{n\geq 1}$ converges to the function $F\;:\!=\;f_{\mu_m}\circ \cdots \circ f_{\mu_1}\circ f$ . As $f_{\mu_m}\circ \cdots \circ f_{\mu_1} (z) $ is a non-constant holomorphic function and $F = -1$ on U, it follows that f is constant on U, as desired.

Proof of Theorem 5·1. Assume for the purpose of a contradiction that there exists $\lambda_0 \in \mathcal{D}_\Delta^1$ with $\lambda_0 \not \in \mathcal{A}_\Delta$ . We note that by Lemma 2·10 we know $\lambda_0 \neq 0$ . Throughout the proof denote U for an open neighbourhood of $\lambda_0$ on which the family $\mathcal{R}_\Delta$ is normal; we may assume $0 \not \in U$ by taking U small enough. Assume first that $\lambda_0$ is not purely imaginary. Consider the real number $c={- |\lambda_0|^2}/{2\textrm{Re}\,\lambda_0}$ and notice that

\begin{align*}\frac{\lambda_0^2}{\lambda_0+c} = 2\textrm{Re}\,\lambda_0 \in\mathbb R.\end{align*}

Choose two sequences of rooted graphs $\{G_n,v_n\}_{n\geq 1}$ , $\{(H_n,w_n)\}_{n\geq 1}$ in $\mathcal{G}_\Delta^1$ so that the sequences of ratios $\{R_{G_n,v_n}(\lambda_0)\}_{n\geq 1}$ and $\{R_{H_n,w_n}(\lambda_0)\}_{n\geq 1}$ converge to respectively 1 and c. By Lemma 5·5 we must have that these sequences of ratios converge locally uniformly on U to the respective constants 1 and c.

Consider the sequence of graphs $\widetilde{G}_{n\geq 1}$ constructed by merging $v_n$ and $w_n$ and by then connecting this vertex to a vertex $\widetilde{v}_n$ . See Figure 3 for an illustration.

Fig 3.

The rooted graph $\widetilde G_n$ in the proof of Theorem 5·1.

It follows from Lemma 2·6 and Lemma 2·9 for all $\lambda \in U$ that

\begin{align*}R_{\widetilde G_n,\widetilde v_n}(\lambda)=\frac{\lambda}{1+\lambda^{-1}R_{G_n,v_n}(\lambda)\,R_{H_n,w_n}(\lambda)},\end{align*}

where we use $0 \not \in U$ . Therefore the sequence of holomorphic functions $\{R_{\widetilde G_n,\widetilde v_n}\}_{n\geq 1}$ converges locally uniformly on U to the function $f(\lambda)={\lambda^2}/({\lambda+c})$ as $n\to \infty$ . Note that f is not a constant function, and that $f(\lambda_0)\in\mathbb R$ , contradicting Lemma 5·5. This contradiction completes the proof for $\lambda_0$ not purely imaginary.

Assume instead that $\lambda_0$ is purely imaginary and let $(G,v)\in\mathcal{G}_\Delta^1$ so that $R_{G,v}(\lambda_0)$ is not purely imaginary. For $c\in \mathbb{R}$ to be determined later choose again two sequences of rooted graphs $\{G_n,v_n\}_{n\geq 1}$ , $\{(H_n,w_n)\}_{n\geq 1}$ in $\mathcal{G}_\Delta^1$ such that sequences $\{R_{G_n,v_n}(\lambda_0)\}_{n\geq 1}$ and $\{R_{H_n,w_n}(\lambda_0)\}_{n\geq 1}$ converge to 1 and c respectively. Define for each $n\geq 1$ , $(\widetilde{G}_n,\widetilde{v}_n)$ as above and let $(K_n,v_n)$ be the rooted graph obtained from the disjoint union of $(\widetilde{G}_n,\widetilde{v}_n)$ and (G, v) by identifying the vertex $\widetilde v_n$ with v. It follows from Lemma 2·6 and Lemma 2·9 for $\lambda \in U$ that

\begin{align*}R_{K_n,v_n}(\lambda)=\frac{R_{G,v}(\lambda)}{1+\lambda^{-1}R_{G_n,v_n}(\lambda)\,R_{H_n,w_n}(\lambda)},\end{align*}

where we use $0 \not \in U$ . Thus in order to follow the same argument as before we require $c \in \mathbb R$ for which

\begin{align*}\frac{\lambda_0 \cdot R_{G,v}(\lambda_0)}{\lambda_0 + c} \in \mathbb R.\end{align*}

It is clear that such real number c exists, hence the identical argument leads to the desired contradiction.

Proof. Because $\overline{\mathcal{Z}_\Delta} = \mathcal{A}_\Delta$ there exists $\lambda_2$ arbitrarily close to $\lambda_0$ for which there is a graph G of maximum degree at most $\Delta $ such that $Z_G(\lambda_2) = 0$ . We claim that we can assume $\lambda_2 \not \in \mathbb{R}$ . This is clear if $\lambda_0 \not \in \mathbb{R}$ . Moreover, if $\lambda_0 \in \mathbb{R}$ then $\lambda_0$ is a strictly positive real number. Because $Z_G(x) > 0$ for any positive real number x, it follows that $\lambda_2$ is necessarily not real as long as it is sufficiently close to $\lambda_0$ .

By Lemma 2·3 there is a rooted tree $(T,v) \in \mathcal{G}_\Delta^1$ such that $R_{T,v}(\lambda_2) = -1$ . Since the rational function $\lambda \mapsto R_{T,v}(\lambda)$ is non-constant, it is an open map. The image of a neighbourhood of $\lambda_2$ therefore contains a small open real interval around $-1$ . Recall that Lemma 3·2 states that for $\mu \in (\!-\!\infty, -1/4)$ the map $f_\mu\;:\;z \mapsto \mu/(1+z)$ is conjugate to a rotation $w \mapsto e^{i \theta} \cdot w$ . Furthermore, by comparing ${\mathrm{tr}}^2$ of both maps, it is not hard to see that those parameters $\mu$ for which $f_\mu$ is conjugate to an irrational rotation lie dense in $(\!-\!\infty, -1/4)$ . Therefore we can choose a $\lambda_1 \in \mathbb{C} \setminus \mathbb{R}$ arbitrarily close to $\lambda_2$ such that for $\mu\;:\!=\;R_{T,v}(\lambda_1)$ the map $f_\mu$ is conjugate to an irrational rotation. From now on $\mu$ is fixed to be this value.

Let p, q be the two fixed points of the transformation $f_\mu$ . In Section 3.1 we explained that $\hat{\mathbb C} \setminus \{p,q\}$ is foliated by generalized circles invariant under $f_\mu$ , and on which $f_\mu$ acts conjugate to an irrational rotation. We denote the generalized circle through z by $C_z$ , and write $C_q$ and $C_p$ for $\{q\}$ and $\{p\}$ respectively. The map $z \mapsto C_z$ is continuous as a map from $\hat{\mathbb{C}}$ to the space $\{K \subseteq \hat{\mathbb C}\;:\;K \text{ compact}\}$ equipped with the Hausdorff metric.

Our aim is to show that $\mathcal{R}^1_\Delta(\lambda_1)$ is dense in $\hat{\mathbb{C}}$ . We first claim that if $w \in \mathcal{R}^1_\Delta(\lambda_1)$ , then $\mathcal{R}^2_\Delta(\lambda_1) \cap C_w$ is dense in $C_w$ .

To prove the claim, let $(H,u) \in \mathcal{G}_\Delta^1$ be a rooted graph such that $R_{H,u}(\lambda_1) = w$ . Let $\widetilde{G}_n$ as follows be obtained from the path $P_{n+1}$ on $n+1$ vertices, labeled $v_0$ up to $v_{n}$ , by implementing (H, u) at $v_0$ and the rooted tree (T, v) at the remaining n vertices of $P_{n+1}$ , see Figure 4. Now by Lemma 2·6 we have

\[R_{\widetilde{G}_n, v_{n}}(\lambda_1) = f_\mu^n(R_{H,u}(\lambda_1)) = f_\mu^n(w).\]

Observe that for each $n\geq 1$ we have $(\widetilde{G}_n, v_n)\in \mathcal{G}_\Delta^2$ . Because $f_\mu$ acts conjugately to an irrational rotation on $C_w$ it follows that $\mathcal{R}^2_\Delta(\lambda_1) \cap C_w$ is dense in $C_w$ .

Fig 4.

The graph $(\widetilde{G}_n, v_n)$ in the proof of the claim.

Because $\mu \in \mathcal{R}^1_\Delta(\lambda_1)$ and $C_\mu = \hat{\mathbb{R}} \;:\!=\; \mathbb{R} \cup \{\infty\}$ it follows from the claim that $\mathcal{R}^2_\Delta(\lambda_1) \cap \hat{\mathbb{R}}$ is dense in $\hat{\mathbb{R}}$ . Observe that $f_{\lambda_1}(\hat{\mathbb{R}}) = \lambda_1 \cdot \hat{\mathbb{R}}$ . So by attaching a vertex at the root with an edge, we obtain that $\mathcal{R}^1_\Delta(\lambda_1) \cap \lambda_1 \cdot \hat{\mathbb{R}}$ is dense in $\lambda_1 \cdot \hat{\mathbb{R}}$ .

The set

\[ U = \{z \in \hat{\mathbb{C}}:\text{$C_z$ intersects $\lambda_1 \cdot \hat{\mathbb{R}}$ transversely}\}\]

is an open set in $\hat{\mathbb{C}}$ , see Figure 5. Because $\lambda_1 \not \in \mathbb{R}$ we see that $C_{-1} = \hat{\mathbb{R}}$ intersects $\lambda_1 \cdot \hat{\mathbb{R}}$ transversely, and thus $-1 \in U$ . The set U is contained in $\cup_{w \in \lambda_1 \cdot \hat{\mathbb{R}}} C_w$ . Because $\mathcal{R}^1_\Delta(\lambda_1) \cap \lambda_1 \cdot \hat{\mathbb{R}}$ is dense in $\lambda_1 \cdot \hat{\mathbb{R}}$ , it follows that $\cup_{w \in \mathcal{R}^1_\Delta(\lambda_1)} C_w$ is dense in U. From the claim we proved earlier, it follows $\mathcal{R}^2_\Delta(\lambda_1)$ is dense in U. Attaching a vertex to the root of a tree in $\mathcal{G}_\Delta^2$ with ratio r yields a rooted tree in $\mathcal{G}_\Delta^1$ with ratio $f_{\lambda_1}(r)$ , and thus $\mathcal{R}^1_\Delta(\lambda_1)$ is dense in the neighbourhood $U_\infty \;:\!=\; f_{\lambda_1}(U)$ of $\infty$ .

Fig 5.

The generalised circles $\lambda_1 \cdot \hat{\mathbb{R}}$ and $\hat{\mathbb{R}}$ intersect in the points 0 and $\infty$ . A region around 0 is drawn. The open set U is shaded in gray. Examples of generalised circles $C_w$ that intersect $\lambda_1 \cdot \hat{\mathbb{R}}$ transversely are drawn with dashed lines, while examples of circles that do not intersect $\lambda_1 \cdot \hat{\mathbb{R}}$ are drawn with dotted lines.

For two rooted trees $(T_1, v_1)\in\mathcal{G}_\Delta^1$ and $(T_2, v_2)\in\mathcal{G}_\Delta^2$ with ratios $r_1$ and $r_2$ respectively we can define the rooted tree $(T_3,v_1) \in \mathcal{G}_\Delta^2$ by adding an edge between the roots of $T_1$ and $T_2$ and considering $v_1$ the root of the obtained tree. By Lemma 2·6 the ratio of $(T_3,v_1)$ is given by

\[ F(r_1,r_2)\;:\!=\;f_{r_1}(r_2)=\frac{r_1}{1+r_2}\]

under the assumption that this fraction is well defined, i.e., $(r_1,r_2) \not \in \{(0,-1),(\infty,\infty)\}$ . It is not hard to see that

\[ F(U_\infty \times \hat{\mathbb{R}}\setminus \{(0,-1),(\infty,\infty)\}) = \hat{\mathbb{C}}.\]

Because $\mathcal{R}^1_\Delta(\lambda_1)$ is dense in $U_\infty$ and $\mathcal{R}^2_\Delta(\lambda_1)$ is dense in $\hat{\mathbb{R}}$ it follows that $\mathcal{R}^2_\Delta(\lambda_1)$ is dense in $\hat{\mathbb{C}}$ . We finally conclude that $\mathcal{R}^1_\Delta(\lambda_1)$ is dense in $f_{\lambda_1}(\hat{\mathbb{C}})=\hat{\mathbb{C}}$ .

Proof. Let $\lambda_0 \in \mathcal{A}_\Delta$ . If $\lambda_0 \in \mathbb C \setminus \mathbb{R}_{\leq 0}$ , then $\lambda_0 \in \overline{\mathcal{D}_\Delta}$ follows from Theorem 5·6.

We know $\overline{\mathcal{Z}_\Delta} = \mathcal{A}_\Delta$ . By Remark 2·11 we know that

\begin{align*}\overline{\mathcal{Z}_\Delta} \cap \mathbb{R}_{\leq 0}= \mathbb{R}_{\leq 0} \setminus int(\Lambda_\Delta)\end{align*}

for all $\Delta \geq 3$ . Proposition 6 of [ Reference Bezáková, Galanis, Ann Goldberg and ŠtefankovičBGGŠ20 ] implies that $\mathbb{C} \setminus (\mathbb{R}\cup \Lambda_\Delta) \subseteq \overline{\mathcal{D}_\Delta}$ for $\Delta \geq 3$ . Hence it follows that $\mathbb{R}_{\leq 0} \setminus int(\Lambda_\Delta) \subseteq \overline{\mathcal{D}_\Delta}$ , which completes the proof.

Proof. Let $\lambda_0\in \mathcal{D}_\Delta.$ Let $(\mathcal{T},U)$ be fast implementer, as guaranteed to exist by Lemma 6·1. For $\lambda$ nearby $\lambda_0$ we still have that the repelling fixed point of $f_\lambda$ is contained in U, its attracting fixed point does not lie in $\overline{U}$ and $\overline{U}\subset f_{\lambda}(U)$ . In other words $(\mathcal{T},U)$ is a fast implementer for $\lambda$ . Therefore applying the algorithm of Lemma 6·2 to $\lambda$ we obtain that the collection of values $\{R_{G,v}(\lambda)\mid (G,v)\in \mathcal{G}_\Delta^1\}$ is dense in $\hat{\mathbb{C}}$ and hence $\lambda\in \mathcal{D}_\Delta$ .

Proof. Let $\lambda\in \mathcal{E}_\Delta$ . Then there exists a graph $G=(V,E)$ such that $1/\lambda$ is a root of $P(z)\;:\!=\;z^{|V|}Z_G(1/z)$ . Now P is a monic polynomial and therefore $1/\lambda\in \mathbb{Z}[i]$ (since $\mathbb{Z}[i]$ is integrally closed by Gauss’s lemma). We also know that $|1/\lambda|\leq {\Delta^{\Delta}}/{(\Delta-1)^{\Delta-1}}$ by Lemma 2·10. This proves the lemma.

Proof. We first perform a brute force, but constant time, computation to obtain a fast implementer $(\{(G_1,v_1),\ldots, (G_M,v_M),(\overline{G}_1,\overline{v_1}),\ldots,(\overline{G}_M,\overline{v}_M\},U)$ for $\lambda_0$ . Denote for $i=1,\ldots,M$ , $\mu_i\;:\!=\;R_{G_i,v_i}$ and $\chi_i\;:\!=\;R_{\overline{G}_i,\overline{v_i}}$ and $g_i\;:\!=\; f_{\mu_i} \circ f_{\chi_i}$ .

The algorithm of Lemma 6·2 applied to P now returns in time $poly(\mathrm{size}({\varepsilon,P}))$ a sequence of ratios $\omega_1\ldots,\omega_K\in \{\lambda_0\}\cup\bigcup_{i=1}^M\{\mu_i,\chi_i\}$ that, by Lemma 2·6, correspond to the implementation of the trees $G_i$ and $\overline{G}_i$ on a path with $K=\mathcal{O}(\max{(\log(1/\epsilon),\log(|P|/\epsilon)))}$ vertices. The resulting rooted tree (T, v) has maximum degree at most $\Delta$ and root degree 1 and satisfies $|R_{T,v}(\lambda_0)-P|\leq \varepsilon$ . Denote the rooted tree corresponding to the sequence $\omega_1,\ldots\omega_i$ by $(T_i,u_i)$ . Then $(T_{i+1},u_{i+1})$ is obtained from $(T_i,u_i)$ by adding the edge $\{v_{i+1},u_i\}$ to $T_i$ and gluing a rooted tree $(H,v)\in \{K_1,(G_j,v_j),(\overline{G_j},v_j)\mid j=1,\ldots,M\}$ to $u_{i+1}$ (here $K_1$ denotes a single vertex.) We then have

(6·2) \begin{equation}\left(Z^{\text{in}}_{T_{i+1},u_{i+1}}(\lambda_0),Z^{\text{out}}_{T_{i+1},u_{i+1}}(\lambda_0)\right)=\left(Z^{\text{in}}_{H,v}(\lambda_0)Z^{\text{out}}_{T_i,u_i}(\lambda_0),Z^{\text{out}}_{H,v}(\lambda_0)Z_{T_i}(\lambda_0)\right).\end{equation}

Note that (6·2) describes a simple recurrence to compute $Z^{\text{in}}_{T,v}(\lambda_0)$ and $Z^{\text{out}}_{T,v}(\lambda_0)$ in time linear in the number of vertices of T.

Finally, we remark that $Z^{\text{out}}_{T,v}(\lambda_0)\neq 0$ since $\lambda_0\notin \mathcal{E}_\Delta$ by assumption.

Proof. We will show that for any $\lambda_0\in (\mathcal{D}_\Delta\cap {\mathbb{Q}[i]})\setminus \mathcal{E}_\Delta$ the computational problem #Hard-CoreNorm( $\lambda_0,\Delta$ ) is #P-hard. Since $ \mathcal{D}^1_\Delta$ is an open set and $\mathcal{E}_\Delta$ is finite, this implies the theorem.

This in fact follows directly from the work of [ Reference Bezáková, Galanis, Ann Goldberg and ŠtefankovičBGGŠ20 ]. Let us briefly indicate why. In [ Reference Bezáková, Galanis, Ann Goldberg and ŠtefankovičBGGŠ20 , section 6] the authors show that a polynomial time algorithm for #Hard-CoreNorm( $\lambda_0,\Delta$ ) combined with the statement of Corollary 6·5 for $\lambda_0$ yields an algorithm that on input of a graph G of maximum degree at most $\Delta$ exactly computes $Z_G(1)$ , the number of independent sets of G, in polynomial time in the number of vertices of G. (The algorithm is obtained by cleverly utilising Corollary 6·5 for suitable choices of P and gluing combinations of the obtained trees to G and applying the assumed algorithm for #Hard-CoreNorm( $\lambda_0,\Delta$ ) to the resulting graph.) Since determining $Z_G(1)$ is a known #P-complete problem, this implies that #Hard-CoreNorm( $\lambda_0,\Delta$ ) is #P-hard.