# Subgroups of a free group with every growth rate

Michail Louvaris, Gal Yehuda, Daniel T Wise

► To cite this version:

Michail Louvaris, Gal Yehuda, Daniel T Wise. Subgroups of a free group with every growth rate. 2025. hal-05069797

HAL Id: hal-05069797

https://hal.science/hal-05069797v1

Preprint submitted on 16 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# SUBGROUPS OF A FREE GROUP WITH EVERY GROWTH RATE

MICAIL LOUVARIS, DANIEL T. WISE, AND GAL YEHUDA

ABSTRACT. For every $\alpha \in [1, 2r - 1]$, we show there exists a subgroup $H < F_r$ whose growth rate is $\alpha$.

## 1. INTRODUCTION

An interesting aspect of the coarse geometry of a finitely generated group $\Gamma$ is its growth function

$$f_{(\Gamma,S)}(n) = \#\{g \in \Gamma : \|g\|_S \le n\},$$

defined with respect to a finite generating set $S$ and the associated word length $\|g\|_S$.

The subject originated in Milnor's comparison of Riemannian volume growth with word-metric growth of a fundamental group. Wolf refined this viewpoint, Gromov proved the landmark theorem that a finitely generated group has polynomial growth precisely when it is virtually nilpotent, and Grigorchuk's celebrated 1984 example revealed the landscape also contains groups of intermediate (subexponential) growth.

Our focus will be the exponential growth rate

$$\mathrm{gr}(\Gamma, S) = \lim_{n \to \infty} f_{(\Gamma,S)}(n)^{1/n} \in [1, \infty).$$

Different generating sets yield comparable—though not identical—values, so we fix a preferred $S$ whenever we speak of the growth rate. For a comprehensive treatment of growth rates, see [6].

When $\Gamma$ is a free group $F_r$ of rank $r \ge 2$ and $S$ is the usual free basis, the Cayley graph is the degree $(2r-1)$ tree $T_{2r-1}$. A direct computation shows $\omega(F_r, S) = 2r-1$. If $H \le F_r$ is an arbitrary subgroup we measure its growth by

$$\omega_{F_r}(H) = \lim_{n \to \infty} f_{(H,F_r,S)}(n)^{1/n} \in [1, 2r-1],$$

where $f_{(H,F_r,S)}(n)$ counts the number of words in $H$ of length $n$ (in $T_{2r-1}$). At the extremes, cyclic subgroups have growth 1 while finite-index subgroups share the growth of $F_r$. A natural, question is:

*Which values are attained by $\omega_{F_r}(H)$ as $H$ ranges over all subgroups?*

<footnote>Date: May 15, 2025.</footnote>

<footnote n="2020">2020 Mathematics Subject Classification. 60B20, 05C80, 20E07, 20E05, 20F65.</footnote>

<footnote>Key words and phrases. Growth of groups, free groups, random graphs, non-backtracking matrix. M.L. received funding from the European Union's Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No 101034255. D.T.W. supported by NSERC.</footnote>
<figure><img src="image_2.png" /><figcaption>FIGURE 1. Construction of graph with prescribed growth.</figcaption></figure>

It was proven in [5] that the set of growth rates of finitely generated subgroups of $F_r$ is dense in the interval $[1, 2r - 1]$. It is natural to ask if every $\alpha \in [1, 2r - 1]$ arises as the growth rate of some subgroup. If we restrict to finitely generated subgroups the answer is no, as the growth rate of a finitely generated subgroup is an algebraic number (see Remark 2.1).

However, if $H \le F_r$ is allowed to be infinitely generated, we prove:

**Theorem 1.1 (Main Theorem).** Let $r \ge 2$ and $\alpha \in [1, 2r - 1]$. There exists a subgroup $H \le F_r$ whose growth rate within $F_r$ equals $\alpha$. That is

$$ \omega_{F_r}(H) = \alpha. $$

This is a consequence of the following attractive result, which is of independent interest:

**Theorem 1.2.** Let $J \to B$ be an immersion of graphs where $B$ is a finite bouquet of circles. Let $J_i$ be an increasing sequence of finite connected based subgraphs with $J = \cup_{i=1}^{\infty} J_i$. Let $H = \pi_1 J$ and for each $i$, let $H_i = \pi_1 J_i$, and regard these as subgroups of $F = \pi_1 B$. Then

$$ \lim_{i \to \infty} \omega_F(H_i) = \omega_F(H). $$

1.1. **Sketch of Theorem 1.1.** Theorem 1.1 is proven in Section 3, which describes how to create a sequence of subgraphs to which Theorem 1.2 can be applied.

Every subgroup $H \le F_r$ corresponds to a based graph $G$ immersed in the bouquet $B_r$, and graphs with maximal degree bounded by $2r$ correspond to subgroups of $F_r$. When $G$ is finite, the growth rate of $H$ coincides with the spectral radius of the non-backtracking matrix $B_G$. This is explained in Section 2.2.

Using the density theorem of [5] we choose a sequence of finite graphs $H_1, H_2, \dots$ whose spectra converge to $\alpha$. We glue these graphs together along an infinite path, as shown in Figure 1. It is very intuitive that the growth rate of the resulting (infinite) graph should be $\alpha$ when the arcs joining them are sufficiently long.
## 2. SUBGROUPS OF THE FREE GROUP

Our main tool for studying the subgroups of the free group is through graphs and graph immersions, as popularized by Stallings [11].

For a locally finite graph $G = (V, E)$ and a vertex $v \in V(G)$, denote by $N_G(v)$ the set of edges with (at least) one endpoint equal to $v$.

**Definition 2.1.** Let $A$ and $B$ be two directed graphs. An immersion of graphs is a function $f: A \to B$ mapping vertices to vertices and edges to edges, which is locally injective: $f_v: N_A(v) \to N_B(f(v))$ is injective for each $v \in V(A)$.

**Lemma 2.2.** Let $(A, a)$ and $(B, b)$ be directed based graphs. Let $f: A \to B$ be a basepoint preserving immersion. Then $f_*: \pi_1(A, a) \to \pi_1(B, b)$ is injective.

*Proof.* This holds since the induced cover between universal covers is an immersion of trees, and hence an injection. See [11, prop 5.3]. □

Let $B_r$ be a graph with one vertex and $r$ directed edges. Letting the basepoint of $B_r$ be its vertex, we have $\pi_1 B_r \cong F_r$, where $F_r$ is a free group of rank $r$ whose basis corresponds to the directed loops of $B_r$. If $G$ is a directed graph with an immersion from $G$ to $B_r$ and $v \in V(G)$ is a vertex, then $\pi_1(G, v) \le F_r$ by Lemma 2.2.

**Theorem 2.3.** Let $G = (V, E)$ be an undirected graph whose degrees are bounded by $2r$. Then, $G$ can be labeled and directed so that there is an immersion from $G$ to $B_r$ if and only if every finite subgraph of $G$ can be labeled and directed in such a way.

*Remark.* Theorem 2.3 is more general than what needed for our purposes: we construct an infinite graph by gluing together immersed graphs along a long ray, hence the graph inherits that immersion.

If $G$ is a finite, undirected graph whose vertex degrees are $\le 2r$, then there is an immersion from $G$ to $B_r$. See [4, p. 57], which we revisit in [5, lem 2.2]. Thus we have the following:

**Corollary 2.4.** Let $G = (V, E)$ be an undirected graph whose degrees are bounded by $2r$. Then the edges of $G$ can be labeled and directed so that there is an immersion from $G$ to $B_r$.

*Proof of Theorem 2.3.* The proof is similar to the proof of the de Bruijn–Erdős Theorem [2]. Let $G = (V, E)$ be an undirected graph with maximal degree $2r$. Labeling (and ordering) the edges of $G$ means choosing a function $L: E \to \{1, \dots, r\} \times \{\pm 1\}$, assigning to each edge of $G$ a letter and a direction. We use the notation $L(G)$ for the directed, labeled graph obtained by applying $L$ to $G$. A function $L$ is a proper labeling of $G$ if there is an immersion $L(G) \to B_r$.
Give {$1, \dots, r$} $\times$ {$\pm 1$} the discrete topology, and define $X$ to be the space of all possible labelings (proper or not) of $G$. Then $X$ has the product topology, $X = (\{1, \dots, r\} \times \{\pm 1\})^{E(G)}$. By Tychonoff's theorem, $X$ is compact.

For a finite subgraph $F \subset G$, the following set is closed:

$$X_F = \{L \in X : L \text{ is a proper labeling of } F\}$$

To see this, observe that a labeling $L$ is proper if and only if every vertex $u \in L(G)$ has neither two outgoing edges nor two incoming edges labeled with the same letter. Hence the following set of non-proper labelings is open:

$$X_F^C = \cup_{v \in V(F)} \cup_{e_1 \neq e_2 \in N(v) \times N(v)} \{L : L(e_1) = L(e_2)\}.$$

Moreover, for finite subgraphs $F_1, \dots, F_k$ in $G$, we have

$$X_{F_1} \cap \dots \cap X_{F_k} = X_{F_1 \cup \dots \cup F_m}$$

and since $X_{F_1 \cup \dots \cup F_m} \neq \emptyset$ by our assumption, the sets $\{X_F : F \text{ is a finite subgraph}\}$ satisfy the finite intersection property. The compactness of $X$ implies that $\cap_F X_F \neq \emptyset$, which completes the proof, as any $L \in \cap_F X_F$ is a proper labeling for $G$. $\square$

**2.1. Growth rates of graphs.** Let $G$ be an undirected, connected graph with vertex degrees bounded above by $2r$. Let $L$ be a proper labeling of $G$, and let $v \in G$ be a vertex. By the discussion above, $\Gamma := \pi_1(L(G), v) \le \pi_1(B_r)$. We are interested in the growth rate of $\Gamma$ in $\pi_1 B_r$, with $\pi_1 B_r$ generated by the $r$ labeled edges of $B_r$.

The map $L$ induces an embedding of every closed non-backtracking loop based at $v$ in $G$ in the Cayley graph of $\pi_1 B_r$ (freely generated by the $r$ edges), hence, the growth rate of $\Gamma$ in $F_r$ equals

$$\omega(G) := \lim_{n \to \infty} \mathrm{NB}_v(n)^{1/n},$$

where $\mathrm{NB}_v(n)$ is the number of length $n$ non-backtracking loops based at $v$. The growth rate does not depend on the vertex $v$.

We approach the proof of Theorem 1.1 by constructing a graph $G$ with the appropriate growth rate, as described Section 3.

*Remark.* In general, the graph $G$ and the subgroup $\Gamma = \pi_1 G$ will not be finitely generated. Indeed, there are only countably many finite graphs, so only countably many $\alpha$ could arise. Moreover, every finitely generated subgroup $\Gamma \le F_r$ is $\pi_1$ of a finite immersed graph $G$, so its growth rate is the Perron-Frobenius eigenvalue of the non-backtracking matrix of $G$, and is thus an algebraic number.
## 2.2. Linear algebra cheat sheet.
A major part of our analysis of growth rates of graphs uses Perron-Frobenious Theory for non-negative matrices. A detailed treatment of this subject can be found in many texts, e.g. [10]. We mention the relevant facts for our purposes.

Let $T$ be a finite matrix with non-negative entries.

**Definition 2.5.** $T$ is irreducible if for all $i, j$, there exists $k \in \mathbb{N}$ with $(T^k)_{i,j} > 0$.

By the Perron-Frobenious Theorem, the leading eigenvalue $\lambda_1(T)$ of an irreducible non-negative matrix $T$ is a positive number, with an eigenvector with positive entries.

**Lemma 2.6.** Let $T$ be an irreducible non-negative matrix. Then,

(1) $\limsup_{k \to \infty} ((T^k)_{i,j})^{1/k} = L$ for all $i, j$. (So the limit is independent of $i, j$).

(2) $L = \lambda_1(T)$, the Perron-Frobenius eigenvalue of $T$.

*Remark.* If $T$ is aperiodic, we can replace the $\limsup$ with $\lim$.

Let $G = (V, E)$ be a graph. Denote by $\vec{E} = \{(u, v) : \{u, v\} \in E\}$ the set of oriented edges of $G$.

**Definition 2.7.** The non-backtracking matrix of $G$ is the $|\vec{E}| \times |\vec{E}|$ matrix $B_G$ with entries:

$$ (B_G)_{e,f} = \begin{cases} 1 & \text{if } e = (u, v) \text{ and } f = (z, w) \text{ where } v = z \text{ and } u \neq w \\ 0 & \text{otherwise.} \end{cases} $$

If $G$ is a finite connected graph with minimal degree $\ge 2$, that is not a cycle, then $B_G$ is irreducible [3]. Thus, $\lambda_1(B_G) = \limsup_n (B_{e,f}^n)^{1/n} = \omega(G)$ by Lemma 2.6.

Our goal is to construct a graph with given growth rate. As discussed above, the graph will generally be infinite so we need to extend the theory to infinite graphs and matrices. If $G$ is locally finite and $B_G$ is irreducible, the equality $\limsup_n (B_{e,f}^n)^{1/n} = \omega(G)$ remains true: $\omega(G) = \lim_{n \to \infty} \mathrm{NB}_v(n)^{1/n}$ for $v \in V(G)$, and

$$ (1) \qquad \mathrm{NB}_v(n) = \sum_{e=(v, \cdot)} \sum_{f=(\cdot, v)} B_{e,f}^n $$

so $\limsup_n \mathrm{NB}_v(n)^{1/n} = \max_{e,f}\{\limsup_n (B_{e,f}^n)^{1/n}\}$. Since $G$ is locally finite, the sum in (1) is finite, and since $B$ is irreducible, $\limsup_n (B_{e,f}^n)^{1/n}$ does not depend on $e, f$, which concludes the result.

Let $T$ be an infinite (countable) matrix, so that $T_{i,j}^k < \infty$ for all $i, j, k$. Definition 2.5 extends naturally to the infinite case, and Lemma 2.6.(1) remains true [8]. It follows that if $G$ is an infinite, locally finite, connected graph with minimal degree
$\ge 2$, and contains a cycle, then $B_G$ satisfies the condition of Lemma 2.6 and
$\omega(G) = \lim \sup_k \{(B_{e,e'}^k)^{1/k}\}$.

The following result will enable us to compute $\omega(G)$ using finite approximations.
For an infinite matrix $T$ and an integer $n$, denote by $T_n$ the $\{1, \dots, n\} \times \{1, \dots, n\}$
submatrix of $T$, and by $\omega(T) = \sup_k \{(T_{i,j}^k)^{1/k}\}$.

**Lemma 2.8 ([9, thm 3]).** Let $T$ be an infinite, irreducible non-negative matrix, with $T_{i,j}^k < \infty$ for all $i,j,k$. Let $\{R_n\}_{n \in \mathbb{N}}$ be a subsequence of $\mathbb{N}$ with $T_{R_n}$ irreducible for all $R_n$. Then $\omega(T) = \sup_n \omega(T_{R_n})$.

**Definition 2.9 (Core).** Let $D$ be a based connected graph. The core of $D$ is the smallest connected based subgraph $D' \subset D$ containing all cycles of $D$. Note that $D'$ is either a single vertex, or $D'$ contains a cycle and has the property that each vertex has degree $\ge 2$. Furthermore, the inclusion $D' \to D$ induces an isomorphism $\pi_1 D' \to \pi_1 D$. See [11].

We now have all the ingredients for proving Theorem 1.2.

*Proof of Theorem 1.2.* Let $J'$ be the based core of $J$. If $J'$ is finite, the claim holds trivially, so we assume $J'$ is infinite and locally finite. The minimal degree in $J'$ is 2, and $J'$ contains a cycle. The following suffices to prove $B_{J'}$ is irreducible: Any directed edges $i, j$ of $J'$, are contained in a finite subgraph $X$ of $J'$ with minimal degree 2, such that $K$ contains a cycle but $K$ is not a cycle. Thus by [3, prop 2.3] the non-backtracking matrix of $X$ is irreducible, hence $B_X^k(i, j) \neq 0$ for some $k$. This implies $B_{J'}^k(i, j) \neq 0$.

Let $\{J_i\}$ be an increasing sequence subgraphs with $J = \cup_i J_i$. It suffices to prove
the claim for their cores $\{J'_i\}$ as they have the same $\pi_1$. For sufficiently large $i$, each
$J'_i$ has a cycle and minimal degree 2, so $\{B_{J'_i}\}$ is a sequence of irreducible truncations
of $B_{J'}$, and so we can apply Lemma 2.8. Observe that $\omega_F(\pi_1 J'_i) \le \omega_F(\pi_1 J'_{i+1})$ since
$J'_i$ is a subgraph of $J'_{i+1}$, so we can replace $\sup$ by $\lim$ in Lemma 2.8. $\square$

3. CONSTRUCTING A GRAPH WITH A GIVEN GROWTH RATE

The goal of this section is to prove:

**Theorem 3.1.** Let $r \in \mathbb{N}$ and $\alpha \in (1, 2r-1)$. There exists a graph $G$ with degrees bounded by $2r$, such that $\omega(G) = \alpha$.

The statement of Theorem 3.1 with $\alpha \in \{1, 2r-1\}$ is also valid as we can let $G$
be an immersed circle or $2r$-regular graph.

The construction is conceptually simple: it was shown in [5] that given $\alpha$ and $\epsilon > 0$, there exists a finite graph $H$ with $|\omega(H) - \alpha| \le \epsilon$.
Starting with a sequence of finite graphs {$H_n$} whose growth rates converge to $\alpha$, one can “glue” them together along an infinite path, as in Figure 1.

The first obstacle to implementing the idea is that some of the graphs we obtain by the method in [5] might have a growth rate larger than $\alpha$. The growth rate of a graph is at least the growth rate of any of its subgraphs, so we ensure $\omega(H_n) < \alpha$.

**Lemma 3.2.** Let $\alpha \in (1, 2r - 1)$. There is a sequence of graphs {$H_n$}$_{n \in \mathbb{N}}$ such that:

(1) For all $n$, $H_n$ is connected, the degrees of $H_n$ are in $\{2, \dots, 2r\}$, and there is at least one vertex $v_n \in V(H_n)$ such that $\deg(v_n) < 2r$.

(2) $\lim_{n \to \infty} \omega(H_n) = \alpha$ and, $\omega(H_n) < \omega(H_{n+1}) < \alpha$ for all $n$.

*Proof.* Let $\beta \in (1, 2r-1)$. By [5, thm 3.2], there exists a sequence of graphs {$T_k$}$_{k \in \mathbb{N}}$ such that $|\omega(T_k) - \beta| \le \frac{C}{\log k}$ for some constant $C$. We construct the sequence $H_n$. To get $H_1$, invoke the Theorem with $\beta_1 = \alpha - \epsilon_1$ for some $\epsilon_1 > 0$. We get a sequence $\{T_k\}$ so that $|\omega(T_k) - \alpha + \epsilon_1| \le \frac{C}{\log k}$, thus there is some $k$ with $T_k$ satisfying $\omega(T_k) < \alpha$. Set $H_1$ to be this $T_k$. Observe that [5, thm 3.2] guarantees that the degrees of $T_k$ are in $\{2, \dots, 2r\}$ and that $T_k$ is connected. Since $\omega(T_k) < \alpha < 2r-1$, there is a vertex with degree $< 2r$.

Continue the construction similarly. To get $H_n$, invoke the Theorem with $\beta_n = \alpha - \epsilon_n$, where $0 < \epsilon_n < \alpha - \omega(H_{n-1})$ and $\epsilon_n \to 0$. $\square$

Another ingredient in the gluing-along-infinite-path construction is gluing. But gluing where? Lemma 3.3 gives a quantitative answer.

**Lemma 3.3.** Let $G_1$ and $G_2$ be two finite graphs, whose minimal degree is at least 2 and where both $G_1$ and $G_2$ are not cycles. Create a new graph $G_3$ by connecting a path of length $k$ to $G_1$ from one end, and to $G_2$ from the other end. Then $\omega(G_3) = \max\{\omega(G_1), \omega(G_2)\} + \epsilon(k)$, where $\epsilon(k) \to 0$ as $k \to \infty$. More precisely, $\epsilon(k) \le C/m^k$, where $m = \max\{\omega(G_1), \omega(G_2)\}$.

*Proof.* The proof uses linear algebra. By the discussion in 2.2, $\omega(G) = \lambda_1(B_G)$.

We use the Collatz-Wielandt formula for non-negative matrices (see e.g. [1, p. 31]): Let $A$ be an irreducible, $n \times n$ real matrix such that $A_{i,j} \ge 0$, and let $x \in \mathbb{R}^n$ be a vector such that $x_i > 0$. Then $\lambda_1(A) \le \max_{i \in [n]} \frac{(Ax)_i}{x_i}$.

Let $u \in G_1$ and $v \in G_2$ be the vertices in $G_1$ and $G_2$ which are connected to the $k$-path $u = w_0, w_1, \dots, w_k = v$, let $B_1, B_2, B_3$ be the non-backtracking matrices of $G_1, G_2, G_3$ respectively, and let $x_1$ and $x_2$ be the Perron-Frobenius eigenvectors of $B_1$ and $B_2$; i.e. $x_{1,i}, x_{2,i} > 0$ and $B_1x_1 = \lambda_1(B_1)x_1, B_2x_2 = \lambda_1(B_2)x_2$. By [3, prop 2.3], both $B_1$ and $B_2$ are irreducible.
Denote the maximal eigenvalue $m = \max\{\lambda_1(B_1), \lambda_1(B_2)\}$. Define the vector $\tilde{x}$, indexed by directed edges in $G_3$ as follows where we choose $C_0, C_1$ later:

$$ \tilde{x}(e) = \begin{cases} x_1(e) & \text{if } e \in G_1 \\ x_2(e) & \text{if } e \in G_2 \\ m^{-t-k-1}C_0 & \text{if } e = (w_{t-1}, w_t) \\ m^{-t}C_1 & \text{if } e = (w_t, w_{t-1}) \end{cases} $$

Observe that this gives a non-zero value for every directed edge of $G_3$. Our goal now is to bound $\max_{e \in G_3} f(e)$ with $f(e) := \frac{B_3 \tilde{x}(e)}{\tilde{x}(e)}$.

Let $e \in G_1$ such that both endpoints of $e$ are different from $u$. Then by our definition $f(e) = \lambda_1(B_1)$. Similarly, if $e \in G_2$ such that both endpoints are different from $v$, then $f(e) = \lambda_1(B_2)$.

Let $e = (x, u)$ be an edge entering $u$ (not from the added path). Then

$$ \frac{B_3 \tilde{x}(e)}{\tilde{x}(e)} = \frac{\sum_{e^{-1} \neq h = (u,t)} \tilde{x}(h) + \tilde{x}((u, w_1))}{\tilde{x}(e)} = \lambda_1(B_1) + \frac{m^{-k} C_0}{\tilde{x}(e)} $$

Let $e = (w_{t-1}, w_t)$ be an edge on the path with $w_{t+1} \neq v$. Then

$$ \frac{B_3 \tilde{x}(e)}{\tilde{x}(e)} = \frac{m^{-t-k} C_0}{m^{-t-k-1} C_0} = m. $$

Let $e = (w_{k-1}, v)$.

$$ (2) \qquad \frac{B_3 \tilde{x}(e)}{x(e)} = \frac{\sum_{(v,t)=h \neq e^{-1}} \tilde{x}(h)}{C_0 m}, $$

and pick $C_0$ so that (2) is smaller than $m$ (this does not depend on $k$).

Let $e = (t, v)$ be an edge entering $v$. Then

$$ \frac{B_3 \tilde{x}(e)}{\tilde{x}(e)} = \frac{\sum_{e^{-1} \neq h = (t,v)} \tilde{x}(h) + \tilde{x}((v, w_{k-1}))}{\tilde{x}(e)} = \lambda_1(B_2) + \frac{m^{-k} C_1}{\tilde{x}(e)}. $$

Let $e = (w_t, w_{t-1})$ be an edge on the path returning to $u$ such that $w_{t-1} \neq u$. Then a similar computation gives $f(e) = m$.

Let $e = (w_1, u)$ be the edge entering $u$ from the path. Then

$$ (3) \qquad \frac{B_3 \tilde{x}(e)}{\tilde{x}(e)} = \frac{\sum_{e^{-1} \neq h = (u,t)} \tilde{x}(h) + \tilde{x}((u, w_1))}{\tilde{x}(e)} = \frac{\sum_{e^{-1} \neq h = (u,t)} \tilde{x}(h)}{C_1 m}, $$

and we choose $C_1$ so that (3) is smaller than $m$.

Overall, $\max_e f(e) \le m + C' m^{-k}$ for some constant $C'$, which proves the claim. $\square$

*Remark.* The constant $C' = C'(G_1, G_2)$ depends on the graphs $G_1, G_2$. We invoke Lemma 3.3 thinking of $G_1$ and $G_2$ as constants, while the parameter $k$ goes to $\infty$.
**3.1. Construction of G.** We construct $G$ in steps. Our main ingredient is the sequence of graphs $\{H_n\}_{n \in \mathbb{N}}$ given by Lemma 3.2. Let $\alpha_n := \omega(H_n)$, with $\lim_{n \to \infty} \alpha_n = \alpha$. Let $G_0$ be a graph with one node, labeled with 1, and no edges.

Let $v_1 \in V(H_1)$ be a vertex whose degree is less than $2r$ in $H_1$. Set $G_1$ to be the graph obtained by “gluing” $H_1$ to $G_0$ by adding an edge from $v_1$ to the vertex labeled 1 in $G_0$. More precisely, $V(G_1) = V(G_0) \cup V(H_1)$ and $E(G_1) = E(G_0) \cup E(H_1) \cup \{1, v_1\}$. The growth rate of $G_1$ is equal to the growth rate of $H_1$.

We proceed to construct $G_2$. By Lemma 3.2, $\alpha_1 < \alpha_2 < \alpha_3$. We attach edges to the vertex $1 \in G_1$: $\{1, 2\}$, $\{2, 3\}$, $\dots \{k_1 - 1, k_1\}$ (where all the vertices labeled with integers are new vertices), and attach the vertex $k_1$ to a vertex $v_2 \in H_2$ with degree less than $2r$. By Lemma 3.3, we can choose $k_1$ so that $\omega(G_2) \in (\alpha_2, \alpha_3)$.

We construct $G_n$ similarly. The important properties of $\{G_n\}$ are that:

(1) $G_n$ is connected and the degrees of $G_n$ are in $\{2, \dots, 2r\}$.

(2) $\omega(G_n) \in (\alpha_n, \alpha_{n+1})$.

(3) $G_n$ is a subgraph of $G_{n+1}$.

The graph $G$ will be the outcome of this process. More formally, $V(G) = \cup_n V(G_n)$ and $E(G) = \cup_n E(G_n)$.

**Theorem 3.4.** $\omega(G) = \alpha$.

*Proof.* This holds by Theorem 1.2. $\square$

<figure><img src="image_3.png" /></figure>

**4. GROWTH RATES AND SPECTRA OF INFINITE GRAPHS?**

Let $B$ be an infinite, non-negative, irreducible matrix as in Subsection 2.2, corresponding (in some sense) to a strongly connected directed graph $G$ — for instance, $B$ may be the adjacency matrix of $G$. Suppose that $B$ has uniformly bounded row and column degrees, so $B$ defines a bounded linear operator on $\ell^p$ for some $p \in [1, \infty]$. A celebrated result in functional analysis, the Krein–Rutman Theorem, states that if $B$ is compact then the spectral radius of $B$ is an eigenvalue. But if $B$ is the adjacency matrix of a directed graph, it is compact iff the number of edges of $B$ is finite.

**Question 4.1.** Under what nontrivial assumptions on $G$, does the growth rate $\omega(B)$ correspond to an eigenvalue of $B$? When is $\omega(B)$ equal to the spectral radius of $B$ as an operator on $\ell^p$?

Using Lemma 2.8, one can show that $\omega(B)$ always belongs to the approximate spectrum of $B$. Moreover, if $B$ is self-adjoint (and hence $G$ is undirected), then $\omega(B)$ is exactly the spectral radius of $B$ acting on $\ell^2$; see [7].
REFERENCES

[1] A. Berman and R. J. Plemmons. *Nonnegative matrices in the mathematical sciences*. SIAM, 1994.

[2] N. d. Bruijn and P. Erdos. A colour problem for infinite graphs and a problem in the theory of relations. *Indigationes Mathematicae*, 13:371–373, 1951.

[3] C. Glover and M. Kempton. Spectral properties of the non-backtracking matrix of a graph. *arXiv preprint arXiv:2011.09385*, 2020.

[4] A. Hatcher. *Algebraic topology*. Cambridge Univ. Press, Cambridge, 2000.

[5] M. Louvaris, D. T. Wise, and G. Yehuda. Density of growth-rates of subgroups of a free group and the non-backtracking spectrum of the configuration model. *arXiv preprint arXiv:2404.07321*, 2024.

[6] A. Mann. *How groups grow*, volume 395. Cambridge university press, 2011.

[7] B. Mohar and W. Woess. A survey on spectra of infinite graphs. *Bulletin of the London Mathematical Society*, 21(3):209–234, 1989.

[8] E. Seneta. Finite approximations to infinite non-negative matrices. In *Mathematical Proceedings of the Cambridge Philosophical Society*, volume 63, pages 983–992. Cambridge University Press, 1967.

[9] E. Seneta. Finite approximations to infinite non-negative matrices, ii: refinements and applications. In *Mathematical Proceedings of the Cambridge Philosophical Society*, volume 64, pages 465–470. Cambridge University Press, 1968.

[10] E. Seneta. *Non-negative matrices and Markov chains*. Springer Science & Business Media, 2006.

[11] J. R. Stallings. Topology of finite graphs. *Invent. Math.*, 71(3):551–565, 1983.

LABORATOIRE D'INFORMATIQUE GASPARD MONGE (LIGM / UMR 8049), UNIVERSITÉ GUSTAVE EIFFELL, MARNE-LA-VALLÉE

Email address: michail.louvaris@univ-eiffel.fr

DEPARTMENT OF MATHEMATICS, WEIZMANN INSTITUTE OF SCIENCE, REHOVOT, ISRAEL

Email address: daniel.wise@weizmann.ac.il

DEPT OF MATH, YALE, NEW HAVEN, USA

Email address: gal.yehuda@yale.edu