Justin Salez

Spectral atoms of unimodular random trees

We use the Mass Transport Principle to analyze the local recursion governing the resolvent (A-z) -1 of the adjacency operator of unimodular random trees. In the limit where the complex parameter z approaches a given location λ on the real axis, we show that this recursion induces a decomposition of the tree into finite blocks whose geometry directly determines the spectral mass at λ. We then exploit this correspondence to obtain precise information on the purepoint support of the spectrum, in terms of expansion properties of the tree. In particular, we deduce that the pure-point support of the spectrum of any unimodular random tree with minimum degree δ ≥ 3 and maximum degree ∆ is restricted to finitely many points, namely the eigenvalues of trees of size less than ∆-2 δ-2 . More generally, we show that the restriction δ ≥ 3 can be weakened to δ ≥ 2, as long as the anchored isoperimetric constant of the tree remains bounded away from 0. This applies in particular to any unimodular Galton-Watson tree without leaves, allowing us to settle a conjecture of Bordenave, Sen and Virág (2013). Finally, we produce explicit examples of non-regular trees whose spectrum is completely atom-free.

Introduction 1.Motivations

Unimodular networks are probability measures on countable rooted graphs satisfying a certain spatial invariance (see below). They were introduced in [START_REF] Benjamini | Recurrence of distributional limits of finite planar graphs[END_REF][START_REF] Aldous | The objective method: probabilistic combinatorial optimization and local weak convergence[END_REF][START_REF] Aldous | Processes on unimodular random networks[END_REF] to describe the geometry of sparse graphs when seen from a uniformly chosen vertex. These local weak limits are often more convenient to work with than the finite-graph sequences that they approximate, and they have been shown to capture the asymptotic behavior of a number of important graph parameters. One emblematic example is the empirical distribution of the eigenvalues λ 1 ≥ . . . ≥ λ |V | of the adjacency matrix:

µ G := 1 |V | |V | k=1 δ λ k . (1)
This fundamental invariant encodes a considerable amount of information about the underlying graph G = (V, E) (see, e.g., the monograph [START_REF] Cvetković | Spectra of graphs[END_REF]), and a vast body of works has been devoted to the understanding of its typical behavior as |V | → ∞, under various models. In the sparse regime |E| = O(|V |), an elegant, unified answer can be given using the framework of local weak limits:

Theorem 1 ( [START_REF] Bordenave | Resolvent of large random graphs[END_REF][START_REF] Abért | Benjamini-Schramm convergence and pointwise convergence of the spectral measure[END_REF][START_REF] Bordenave | Spectrum of random graphs[END_REF]). If a sequence of finite graphs (G n ) n≥1 admits a local weak limit L, then the associated sequence of empirical spectral distributions (µ Gn ) n≥1 admits a weak limit µ L ∈ P(R).

Moreover, the convergence holds in the Kolmogorov-Smirnov metric:

sup λ∈R |µ Gn ((-∞, λ]) -µ L ((-∞, λ])| ---→ n→∞ 0.
The construction of µ L relies on the spectral theorem for self-adjoint operators on Hilbert spaces, and will be recalled later. The essential message is that the asymptotic spectral analysis of large sparse graphs can, in principle, be performed directly at the level of their local weak limits. This program was initiated in [START_REF] Bordenave | Resolvent of large random graphs[END_REF][START_REF] Bordenave | The rank of diluted random graphs[END_REF] and continued in [START_REF] Bordenave | On quantum percolation in finite regular graphs[END_REF][START_REF] Bordenave | Mean quantum percolation[END_REF], see also the related preprints [START_REF] Backhausz | Spectral measures of factor of i.i.d. processes on vertex-transitive graphs[END_REF][START_REF] Rahman | A lower bound on the spectrum of unimodular networks[END_REF][START_REF] Jung | Delocalization and Limiting Spectral Distribution of Erd\H{o}s-R\'{e}nyi Graphs with Constant Expected Degree[END_REF]. The recent survey [START_REF] Bordenave | Spectrum of random graphs[END_REF] contains a thorough exposition of the current state of the art, as well as a list of open problems. Not much is known about µ L , even in the important special case where L is a unimodular Galton-Watson tree, i.e., a random rooted tree obtained by a Galton-Watson branching process where the root has a given offspring distribution π = (π k ) k≥0 (with finite, non-zero mean) and all descendants have the size-biased offspring distribution π = ( π k ) k≥0 defined by

π k = (k + 1)π k+1 i iπ i . (2)
This simple unimodular network -henceforth denoted by ugwt(π) -plays a distinguished role in the theory, since it is the local weak limit of large random graphs with asymptotic degree distribution π [START_REF] Bordenave | Lecture notes on random graphs and probabilistic combinatorial optimization[END_REF]. Two popular examples are the Erdős-Rényi model with fixed average degree c (π = Poisson(c)), and the random r-regular graph (π = δ r ). In the latter case, ugwt(π) is the infinite r-regular tree, whose spectrum is the Kesten-McKay distribution [START_REF] Mckay | The expected eigenvalue distribution of a large regular graph[END_REF] visible on Figure 1:

µ ugwt(δr) (dλ) = r 4(r -1) -λ 2 2π(r 2 -λ 2 ) 1 (-2 √ r-1,2 √ r-1) (λ) dλ. (3)
Apart from this degenerate case, an explicit description of µ ugwt(π) seems out of reach at present, and our understanding remains extremely limited. For example, the following question was raised by Bordenave, Sen and Virág [START_REF] Bordenave | Mean quantum percolation[END_REF]Question 1.8] and reiterated in [9, Question 4.5]:

Question 1. If π has finite support and π 1 = 0, does µ ugwt(π) admit only finitely many atoms ?

The aim of the present work is to provide a general understanding of the atomic mass µ L ({λ}) assigned to an arbitrary point λ ∈ R, for any unimodular network L that is concentrated on trees. Our main contribution is a general formula relating µ L ({λ}) to the geometry of the connected components of a certain induced subgraph, see Theorem 2. Among other consequences, we answer Question 1 in the affirmative, and prove that the conclusion actually extends to any unimodular random tree whose anchored isoperimetric constant is bounded away from 0. This includes, in particular, all unimodular random trees with degrees in {δ, . . . , ∆}, for any fixed 3 ≤ δ ≤ ∆ < ∞. In addition, we provide an explicit list of all possible atoms.

Unimodular networks and their spectral measures

We only recall the necessary definitions, and refer to the excellent survey [START_REF] Bordenave | Spectrum of random graphs[END_REF] for details. Unimodular networks. A rooted graph (G, o) is a graph G = (V, E) together with a distinguished vertex o ∈ V , called the root. An isomorphism between two rooted graphs is a graph isomorphism which additionally maps the root to the root. We let G denote the set of isomorphism classes of connected, locally finite rooted graphs on a countable number of vertices. We turn G into a Polish space by defining the distance between (G, o) and (G , o ) to be 1/(1 + R) where

R = sup{r ≥ 0 : B r (G, o) is isomorphic to B r (G , o )}. (4)
Here, B r (G, o) is the ball of radius r around o in G, viewed as a rooted graph. Uniform rooting is a natural procedure for turning a finite graph G = (V, E) into a G -valued random variable: declare a uniformly chosen vertex o ∈ V as the root, restrict the graph to its connected component, and forget the labels. If (G n ) n≥1 is a sequence of finite graphs and if the sequence of laws induced by uniform rooting admits a limit L in the usual weak sense for Borel probability measures on Polish spaces, we call L the local weak limit of (G n ) n≥1 . Uniform rooting confers to L a powerful invariance: let G be the natural analogue of G for doubly-rooted graphs (G, x, y); a G -valued random variable

(G, o) (rather, its law L) is called unimodular if for any Borel function f : G → [0, ∞], E   x∈V (G) f (G, o, x)   = E   x∈V (G) f (G, x, o)   . (5)
One may think of f (G, x, o) as an amount of mass sent from x to o in G: the equality (5) -called the Mass Transport Principle -then expresses the fact that the expected mass received and sent by the root coincide. It is easy to see that the local weak limit of any sequence of finite graphs is unimodular. Whether the converse holds is an open problem with deep implications, see [START_REF] Aldous | Processes on unimodular random networks[END_REF][START_REF] Elek | On the limit of large girth graph sequences[END_REF][START_REF] Benjamini | Unimodular random trees. Ergodic Theory Dynam[END_REF].

Spectral measures. Let G = (V, E) be a countable, locally finite graph. Consider the Hilbert space H = 2 C (V ) and its canonical orthonormal basis (e o ) o∈V , where

e o : x -→ 1 if x = o 0 otherwise. ( 6
)
By definition, the adjacency operator A of G is the linear operator on H whose domain is the (dense) subspace of finitely-supported functions, and whose action on the above basis is given by

e x |Ae y = 1 if {x, y} ∈ E 0 otherwise. (7)
A is symmetric, and this already ensures that A -z is injective for each z ∈ C \ R. If in addition the range of A -z is dense, then A (or G itself) is said to be (essentially) self-adjoint. In that case, the resolvent (A -z) -1 extends to a unique bounded linear operator on H and for each o ∈ V , the spectral theorem for self-adjoint operators (see, e.g. [20, Chapter VII]) yields the representation

e o |(A -z) -1 e o = R 1 λ -z µ (G,o) (dλ), (z ∈ C \ R) (8)
for a unique Borel probability measure µ (G,o) on R known as the spectral measure of the pair (A, e o ). This will be our main object of study. To gain some intuition, consider the case where G is finite: then there is an orthonormal basis of eigenfunctions φ 1 , . . . , φ |V | of A with respective eigenvalues λ 1 , . . . , λ |V | , and we easily compute

µ (G,o) = |V | k=1 |φ k (o)| 2 δ λ k . (9)
In words, µ (G,o) is a mixture of atoms at the eigenvalues of A, their masses being the squared norm of the orthogonal projection of e o onto the corresponding eigenspaces. In particular, we see that

µ G = 1 |V | o∈V µ (G,o) . ( 10
)
Figure 2: Spectral decomposition of a 40-vertex tree at λ = 1: S 1 (in red) consists of 5 connected components, and its boundary ∂S 1 (in yellow) has size 3, so the multiplicity of 1 is 5 -3 = 2.

Since the right-hand side is nothing but an expectation under uniform rooting, it is natural to extend the definition of the spectral distribution (1) to any unimodular network L by setting

µ L (•) := E µ (G,o) (•) where (G, o) ∼ L. (11)
This is the limiting measure appearing in Theorem 1. We emphasize that there are infinite graphs whose adjacency operator is not self-adjoint, see, e.g., [START_REF] Müller | On the spectrum of an infinite graph[END_REF]. However, such pathological graphs have zero measure under any unimodular law (see [

Main results

As explained in the motivations, we seek to develop a general understanding of the mass µ L ({λ}) = E µ (G,o) ({λ}) assigned to an arbitrary λ ∈ R. To this end, let us define the λ-support of a selfadjoint graph G = (V, E) as

S λ := o ∈ V : µ (G,o) ({λ}) > 0 . ( 12
)
When G is finite, it follows from ( 9) that o ∈ S λ if and only if there is an eigenfunction for λ which does not vanish at o. Let us say that a finite graph G = (V, E) is λ-prime if λ is an eigenvalue of the adjacency matrix of G but not of G \ {o}, for any o ∈ V . Note that the eigenvalue λ is then necessarily simple, with a nowhere vanishing associated eigenfunction. We use the standard notation deg S (o) for the number of neighbors of o ∈ V in the subset S ⊆ V , and ∂S for the (external) boundary of S, consisting of those vertices outside S having at least one neighbor in S.

We will use the short-hand ∂o instead of ∂{o} to denote the set of neighbors of o.

Theorem 2. Let L be a unimodular network concentrated on trees, and let λ ∈ R. Then almostsurely under L, the connected components induced by S λ are finite λ-prime trees. Moreover,

µ L ({λ}) = P (o ∈ S λ ) - 1 2 E deg S λ (o)1 (o∈S λ ) -P (o ∈ ∂S λ ) (13) = E   1 (o∈S λ ) |C(S λ , o)|   1 - x∈∂C(S λ ,o) 1 deg S λ (x)     . ( 14
)
where C(S λ , o) denotes the connected component of o in the graph induced by S λ .

The formula ( 13) has a simple interpretation in the case where L is the law induced by uniform rooting of a finite forest: multiplying ( 13) by the number of vertices, we obtain that the total multiplicity of the eigenvalue λ in any finite forest equals the number of connected components of S λ minus |∂S λ |, as illustrated in Figure 2. In fact, the corresponding eigenspace can be completely described: any eigenfunction is zero outside S λ , so its restriction to any connected component of S λ is an eigenfunction of the underlying tree. But the latter is λ-prime, so the solution is unique thereon, up to proportionality. The corresponding coefficients (one for each component) can be freely chosen, subject to the constraint that at each x ∈ ∂S λ , the neighboring entries add to zero.

Our main interest for the above formula lies in its potential to provide explicit information on the pure-point support of the spectral distribution:

Σ p.p. (L) := {λ ∈ R : µ L ({λ}) > 0} . (15)
For example, one of the surprising aspects of Theorem 2 is that, even on infinite trees, the presence of a spectral atom at a given location λ ∈ R ultimately stems from the aggregation of finite λ-prime trees. This implies in particular that λ must belong to the (countable, dense) ring A of totally real algebraic integers, i.e. roots of real-rooted monic polynomials with integer coefficients.

Corollary 3 (Algebraicity). Let L be a unimodular network concentrated on trees. Then,

Σ p.p. (L) ⊆ A. (16)
We note that Corollary 3 also follows by combining Theorem 1 with a result of Elek [START_REF] Elek | On the limit of large girth graph sequences[END_REF] or Benjamini, Lyons and Schramm [START_REF] Benjamini | Unimodular random trees. Ergodic Theory Dynam[END_REF] stating that every unimodular random tree is the local weak limit of some sequence of finite graphs. Theorem 2 provides an intrinsic explanation for algebraicity, without resorting to finite approximation. Whether the conclusion extends to all unimodular networks -and, in particular, to Caylay graphs of finitely generated groups -remains an open problem. Despite its crude appearance, Corollary 3 is actually tight: the main result in [START_REF] Salez | Every totally real algebraic integer is a tree eigenvalue[END_REF] implies that equality holds in [START_REF] Jung | Delocalization and Limiting Spectral Distribution of Erd\H{o}s-R\'{e}nyi Graphs with Constant Expected Degree[END_REF] when L = ugwt(π), for any degree distribution π with full support. However, a much stronger conclusion than ( 16) can be obtained as soon as one restricts the degrees of our unimodular random tree: assume that all degrees lie in {δ, . . . , ∆} for some fixed integers ∆ ≥ δ ≥ 3. Using the obvious fact that |∂S| ≥ |S|(δ -2) + 2 for any finite subset S of vertices, we deduce from the alternative expression ( 14) that

µ L ({λ}) ≤ 1 τ (λ) 1 - (δ -2)τ (λ) + 2 ∆ + ,
where τ (λ) is the tree-complexity of the totally real algebraic integer λ, defined as the minimum possible size of a tree with eigenvalue λ. This crude L ∞ bound has a surprising consequence:

Corollary 4. Fix two integers ∆ ≥ δ ≥ 3.
If L is a unimodular network concentrated on trees with degrees in {δ, . . . , ∆}, then µ L has only finitely many atoms. More precisely,

Σ p.p. (L) ⊆ λ ∈ A : τ (λ) < ∆ -2 δ -2 .
An explicit list of the 11 totally real algebraic integers λ with τ (λ) ≤ 4 is given in Table 1

below. For example, if ∆-2 δ-2 ≤ 2, then Σ p.p. (L) ⊆ {0}, while if ∆-2 δ-2 ≤ 3 then Σ p.p. (L) ⊆ {-1, 0, +1}
, and so on. In the special case of unimodular Galton-Watson trees, Corollary 4 answers Question 1 in the affirmative, under the additional restriction that π 2 = 0. The constraint δ ≥ 3 may actually be relaxed to a control on the isoperimetric constant, defined for any infinite locally finite graph G by

i(G) := inf |∂S| |S| : S ⊆ V (G), 0 < |S| < ∞ . (17)
Indeed, the same argument as above with

|∂S| ≥ |S|(δ -2) + 2 replaced by |∂S| ≥ i(G)|S| yields Corollary 5. Fix ∆ < ∞, i > 0.
If L is a unimodular network concentrated on infinite trees with degrees at most ∆ and isoperimetric constant at least i, then

Σ p.p. (L) ⊆ λ ∈ A : τ (λ) < ∆ i .
However, this is still insufficient to answer Question 1 in full generality, since a unimodular Galton-Watson tree with π 2 > 0 contains arbitrarily long paths made of degree-2 vertices. We will overcome this by exploiting a refinement of the isoperimetric constant known as the anchored isoperimetric constant i (G, o), defined for any (infinite

) rooted graph (G, o) ∈ G by i (G, o) := lim n→∞ inf |∂S| |S| : o ∈ S ⊆ V (G), G S is connected, n ≤ |S| < ∞ . ( 18
)
It is immediate to see that the choice of the root o is irrelevant, and that i (G, o) ≥ i(G). A more elaborate argument than the one used above will allow us to prove the following result.

Theorem 6. Fix ∆ < ∞, i > 0.
If L is a unimodular network concentrated on trees with degrees in {2, . . . , ∆} and anchored isoperimetric constant at least i , then

Σ p.p. (L) ⊆ λ ∈ A : τ (λ) < 3∆ 2 i .
A recent result of Chen and Peres [13, Corollary 1.3] implies that the anchored isoperimetric constant of ugwt(π) is deterministically bounded away from 0 when π 0 = π 1 = 0 and π 2 < 1. This finally allows us to answer Question 1 in the affirmative, as promised at the beginning. Note that if both 1 and ∆ are in the support of π, then for each h ≥ 1, there is a positive probability that ugwt(π) is exactly T ∆,h , the finite ∆-regular tree of depth h. Consequently, Σ p.p. (ugwt(π)) must contain all eigenvalues of the trees T ∆,h , h ≥ 1. Now, it follows from (3) (or by explicit computation) that these eigenvalues are dense in -2 √ ∆ -1, +2 √ ∆ -1 . As a consequence, we obtain the following striking dichotomy for the atomic support of Galton-Watson trees.

Corollary 7 (Dichotomy for ugwt's). Suppose that ∆ := max{k ≥ 1 :

π k > 0} < ∞. Then,
• Either π 1 = 0, and Σ p.p. (ugwt(π)) is reduced to finitely many points.

• Or π 1 > 0, and

Σ p.p. (ugwt(π)) is dense in -2 √ ∆ -1, +2 √ ∆ -1 . Algebraic integer λ 0 ±1 ± √ 2 ± √ 3 ± 1+ √ 5 2 ± 1- √ 5 2 • • • Minimal tree • • • Complexity τ (λ) 1 2 3 4 • • • Table 1:
The totally real algebraic integers λ with tree-complexity τ (λ) ≤ 4.

Finally, our result allows to prove that the spectral measure of certain Galton-Watson trees is completely atom-free. Indeed, when ∆ ≤ 2δ -2, Corollary 4 ensures that Σ p.p. (L) ⊆ {0}. On the other hand, the mass of the atom at 0 has been explicitly computed in [START_REF] Bordenave | The rank of diluted random graphs[END_REF]:

µ ugwt(π) ({0}) = max x∈[0,1] φ(x) + (1 -x)φ (x) + φ 1 - φ (x) φ (1) -1 , (19)
where φ(x) = k π k x k denotes the generating series of π.

Corollary 8 (Atom-free trees). Suppose that π has support {δ, . . . , ∆}, where δ ≤ ∆ ≤ 2δ -2.

Then ugwt(π) is atom-free, i.e. Σ p.p. (ugwt(π)) = ∅, if and only if for all x ∈ [0, 1].

φ(x) + (1 -x)φ (x) + φ 1 - φ (x) φ (1) ≤ 1,
where we recall that φ(x) = k π k x k denotes the generating series of π.

The above criterion is easy to check in practice, since φ is just a polynomial of degree ∆. For a concrete example, we note that π = 1 2 π 3 + 1 2 π 4 does satisfy the conditions of Corollary 8. Consequently, there is no atom in the limiting spectrum of large random graphs with half degree-3 vertices and half degree-4 vertices, answering a question of Eyal Lubetzky (personal communication). We note, however, that the case λ = 0 is special, because there is only one λ-prime tree, namely the single vertex. This simplification yields a simple recursive structure for S 0 which, retrospectively, seems to be the reason behind the existence of the explicit formula [START_REF] Rahman | A lower bound on the spectrum of unimodular networks[END_REF]. In contrast, for each λ ∈ A \ {0}, there are infinitely many λ-prime trees, leaving few hope for a general explicit expression. In particular, the complete characterization of Galton-Watson trees without spectral atoms remains a natural and challenging open problem.

Question 2. For which degree distributions π do we have Σ p.p. (ugwt(π)) = ∅ ?

The remainder of the paper is devoted to the proof of Theorem 2 and Theorem 6. Our starting point is a well-known local recursion governing the resolvent (A -z) -1 of self-adjoint trees.

Spectral decomposition of self-adjoint trees

In this section, we investigate the structure of the λ-support of an arbitrary self-adjoint tree.

The cavity equations

As many graph-theoretical quantities, spectral measures admit a recursive structure when evaluated on trees. This recursion is better expressed in terms of the Stieltjes transform s, defined for any finite Borel measure µ on R by the formula

s(z) := R 1 λ -z µ(dλ). (20)
Note that s is an analytic function from the upper half-plane H = {z ∈ C : (z) > 0} to itself and

sup {|s(z)| × (z) : z ∈ H} < ∞. (21)
Conversely, it is classical that any analytic function s : H → H satisfying ( 21) is the Stieltjes transform of a unique finite Borel measure µ on R, whose total mass is then simply given by the supremum in [START_REF] Salez | Some implications of local weak convergence for sparse random graphs[END_REF]. Now, if µ is a finite measure and s its Stieltjes transform, the equation

s(z) := -1 z + s(z) (22)
defines an analytic function s : H → H satisfying [START_REF] Salez | Some implications of local weak convergence for sparse random graphs[END_REF] with the supremum being 1. Therefore, it is the Stieltjes transform of a unique probability measure on R, which we will denote by µ. The transformation µ → µ will play a crucial role, for the following reason.

Let T = (V, E) be a self-adjoint tree. Deleting a vertex o splits T into deg(o) disjoint subtrees (T x→o : x ∈ ∂o). At the operator-theoretic level, this translates into the orthogonal decomposition

A T \o = x∈∂o A Tx→o (23)
From this identity and the fact that A T is self-adjoint, it easily follows (see, e.g., [START_REF] Salez | Some implications of local weak convergence for sparse random graphs[END_REF]) that the (A Tx→o : x ∈ ∂o) are themselves self-adjoint, and that the spectral measure µ (T,o) is related to the spectral measures µ (Tx→o,x) : x ∈ ∂o via the formula

µ (T,o) = x∈∂o µ (Tx→o,x) . (24)
Similarly, for any y ∈ ∂o, the above formula applied to T o→y instead of T yields

µ (To→y,o) =    x∈∂o\{y} µ (Tx→o,x)    . ( 25
)
We will refer to the local identities ( 24) and (25) as the cavity equations at o and (o, y), respectively. This recursive structure is not new (see, e.g., [START_REF] Bordenave | Resolvent of large random graphs[END_REF][START_REF] Bordenave | The rank of diluted random graphs[END_REF]). Our main contribution here is to investigate the way in which it affects the underlying measures "locally", at a given spectral location λ ∈ R.

Impact at a given spectral location λ ∈ R

Let us now fix a location λ ∈ R and a finite measure µ, and focus on the "local" statistics

α := µ({λ}), β := R 1 (ξ -λ) 2 µ(dξ), γ := R 1 ξ-λ µ(dξ) if β < ∞; ? else. ( 26
)
Note that either α = 0, or β = ∞. We emphasize that we regard γ as undefined (as expressed by the dummy symbol ?) whenever β = ∞, regardless of whether the integral R 1 ξ-λ µ(dξ) actually converges or not: the precise value of this integral will only be relevant when β < ∞. Perhaps surprisingly, the data (α, β, γ) happens to evolve autonomously under the action of [START_REF] Salez | Every totally real algebraic integer is a tree eigenvalue[END_REF], in the sense that the triple ( α, β, γ) corresponding to the measure µ is completely determined by the triple (α, β, γ) only. The precise functional relation is summarized in the following Table .   Proof of the relations in Table 2. The triple (α, β, γ) is directly related to the behavior of the Stieltjes transform s of µ near the spectral location λ. To see this, recall that by definition

s(λ + iε) = R (ξ -λ) + iε (ξ -λ) 2 + ε 2 µ(dξ), (27)
for every ε > 0. Now, let ε → 0. In view of the definitions of α, β, γ, we see that

s(λ + iε) = iα ε + o 1 ε , ( 28
) Possible cases Value of α Value of β Value of γ α > 0 0 1 α 0 α = 0 β < ∞ γ = -λ 1 1 + β ∞ ? γ = -λ 0 1 + β (λ + γ) 2 -1 λ + γ β = ∞ 0 ∞ ?
Table 2: The values of α, β, γ as functions of α, β, γ.

by dominated convergence, and also, by monotone convergence,

β = lim ε→0 + ↑ s(λ + iε) ε . (29)
Moreover, if β < ∞, then it is clear from (27) that we have the lower-order expansion

s(λ + iε) = γ + iβε + o(ε). ( 30
)
Injecting these into [START_REF] Salez | Every totally real algebraic integer is a tree eigenvalue[END_REF] immediately gives access to the behavior of s(λ + iε) as ε → 0 + . From the latter, we may in turn deduce the values of α, β, γ, using (28)-( 29)-(30) with α, β, γ, s replaced by α, β, γ, s, respectively. There are four cases, corresponding to the four rows in Table 2:

• If α > 0 then s(λ + iε) ∼ iε α , implying in turn that β = 1 α and γ = 0. • If β < ∞, γ = -λ 0 then s(λ + iε) ∼ i (1+β)ε , implying α = 1 1+β . • If β < ∞, γ = -λ 0 then s(λ + iε) = -1 λ+γ + iε(1+β) (λ+γ) 2 + o(ε), implying β = 1+β (λ+γ) 2 , γ = -1 λ+γ . • If α = 0, β = ∞ then | s(λ + iε)| ε and s(λ+iε) | s(λ+iε)| 2 ε. Contradictorily, assuming β < ∞, γ = 0 would yield | s(λ + iε)| ∼ βε, assuming β < ∞, γ = 0 would yield s(λ+iε) | s(λ+iε)| 2 ∼ βε γ 2
, and assuming α > 0 would yield s(λ+iε)

| s(λ+iε)| 2 ∼ ε α . Thus, we must have α = 0 and β = ∞. Note that by our convention, we have γ =? in that case. This concludes the proof.

Structure of the λ-support

Let us now fix a self-adjoint tree T = (V, E) and apply the general relations given in Table 2 to the cavity equations ( 24)-(25). For o ∈ V , we let (α o , β o , γ o ) denote the local statistics of the measure µ (T,o) at λ, as defined in (26). We define (α x→o , β x→o , γ x→o ) similarly, with µ (Tx→o,x) instead.

Lemma 9 (Reciprocity relations). Consider a vertex o ∈ S λ . Then

x∈∂o β x→o < ∞ (31) x∈∂o γ x→o = -λ (32) x∈∂o α o β x→o = 1 -α o . ( 33
)
Moreover, for each y ∈ ∂o ∩ S λ ,

γ y→o = 1 γ o→y ( 34
)
α o β y→o = 1 -α y β o→y . ( 35
)
On the other hand, for each y ∈ ∂o \ S λ ,

γ y→o = 0 (36) α o β y→o = α o→y x∈∂y∩S λ α x→y . ( 37
)
Proof. Consider the cavity equation at o: since only the second row in Table 2 yields α > 0, the assumption o ∈ S λ is actually equivalent to the conditions (31)-(32), and we then have the formula

α o = 1 1 + x∈∂o β x→o . ( 38
)
The identity (33) follows immediately. Now, let y ∈ ∂o. The fact that o ∈ S λ ensures that β y→o < ∞, so that γ o→y is well-defined. There are two possible scenarii, depending on its value:

First case: γ y→o = 0. Then (32) fails to hold if ∂o is replaced by ∂o \ {y}. Consequently, the third row in Table 2 applies to the cavity equation at (o, y) and yields

β o→y = 1 + x∈∂o\{y} β x→o λ + x∈∂o\{y} γ x→o 2 (39)
γ o→y = -1 λ + x∈∂o\{y} γ x→o . (40)
Note that by (32), the denominator on the right-hand side of (40) equals -γ y→o , and (34) follows. Now, let us take a look at the cavity equation at (y, o): since only the third row in Table 2 yields γ = 0, the fact that γ y→o = 0 ensures that

γ y→o = -1 λ + x∈∂y\{o} γ x→y . (41)
Replacing the left-hand side by 1/γ o→y and rearranging, we see that

x∈∂y γ x→y = -λ. (42)
Thus, the second row in Table 2 applies to the cavity equation at y, and we conclude that y ∈ S λ . Finally, we may use ( 40) and (34) to rewrite (39) as

1 + x∈∂o\{y} β x→o = β o→y (γ o→y ) 2 = γ y→o β o→y γ o→y ,
which we may then insert into (38) to arrive at

α o = γ o→y γ o→y β y→o + γ y→o β o→y .
By symmetry, the same formula holds with o and y interchanged, and (35) follows.

Second case: γ y→o = 0. Then (31)-(32) continue to hold with ∂o replaced by ∂o \ {y}. Thus, the second row in Table 2 applies to the cavity equation at (o, y) and yields

α o→y = 1 1 + x∈∂o\{y} β x→o . (43)
In particular, α o→y > 0. Thus, the first row in Table 2 applies to the cavity equation at y, and we conclude that y / ∈ S λ . Finally, consider the cavity equation at (y, o): since only the first row in Table 2 yields γ = 0, the assumption γ y→o = 0 ensures that

β y→o = 1 x∈∂y\{o} α x→y . (44)
We may now use (38), ( 43) and (44) successively to write

α o β y→o = β y→o β y→o + 1 αo→y = α o→y α o→y + 1 βy→o = α o→y x∈∂y α x→y .
To obtain (37), it remains to argue that only those x ∈ S λ contribute to the denominator. To see this, consider the cavity equation at (y, x) for an arbitrary x ∈ ∂y \ {o}: since α o→y > 0, the first row in Table 2 guarantees that β y→x < ∞ and γ y→x = 0. In other words, y does not contribute to the criterion for whether α x > 0, and the latter becomes equivalent to the condition α x→y > 0.

Lemma 10. Any vertex in the boundary of S λ actually has at least two neighbors in S λ , i.e.

o ∈ ∂S λ =⇒ deg S λ (o) ≥ 2.
Proof. If o ∈ ∂S λ then by definition, there is some neighbor x of o that lie inside S λ . By (36), we know that γ o→x = 0. Since only the first row in Table 2 yields γ = 0, we deduce that y∈∂o\x α y→o > 0.

In other words, o admits another neighbor y, distinct from x, such that α y→o > 0. This actually implies that y ∈ S λ , as shown at the end of the above proof.

Proofs of the main results

We may finally specialize the above deterministic identities to unimodular random trees, and exploit the Mass Transport Principle to establish Theorems 2 and 6.

Proof of Theorem 2

The main formula [START_REF] Chen | Anchored expansion, percolation and speed[END_REF]. For a self-adjoint tree T = (V, E) and a vertex o ∈ V , we have by ( 35)

deg S λ (o)1 (o∈S λ ) = x∈∂o (α o β x→o + α x β o→x )1 (x∈S λ ) 1 (o∈S λ ) .
Taking expectation at the root of our unimodular random tree, we obtain

E deg S λ (o)1 (o∈S λ ) = E x∈∂o α o β x→o 1 (x∈S λ ) 1 (o∈S λ ) + E x∈∂o α x β o→x 1 (x∈S λ ) 1 (o∈S λ ) .
By the Mass Transport Principle, the two terms on the right-hand side are equal and hence

E x∈∂o α o β x→o 1 (o∈S λ ) 1 (x∈S λ ) = 1 2 E deg S λ (o)1 (o∈S λ ) .
On the other hand, using (37), we have

E x∈∂o α o β x→o 1 (o∈S λ ) 1 (x∈∂S λ ) = E x∈∂o α o→x y∈∂x∩S λ α y→x 1 (o∈S λ ) 1 (x∈∂S λ ) = E x∈∂o α x→o y∈∂o∩S λ α y→o 1 (x∈S λ ) 1 (o∈∂S λ ) = P (o ∈ ∂S λ ) ,
by the Mass Transport Principle again. Adding-up those two identities, we obtain

P (o ∈ ∂S λ ) + 1 2 E deg S λ (o)1 (o∈S λ ) = E x∈∂o α o β x→o 1 (o∈S λ ) = E (1 -α o )1 (o∈S λ ) ,
thanks to (33). Recalling that E[α o ] = µ L ({λ}) concludes the proof of the identity [START_REF] Chen | Anchored expansion, percolation and speed[END_REF].

Finiteness of the connected components. We will use the following general result.

Theorem 11 (Aldous and Lyons [START_REF] Aldous | Processes on unimodular random networks[END_REF][Theorem 6.1). If L ∈ P(G ) is a unimodular network concentrated on infinite graphs, then

E[deg(o)] ≥ 2.
Let S λ denote the restriction of S λ to its infinite connected components. In order to show that S λ = ∅ almost-surely, it is enough to prove P (o ∈ S λ ) = 0, since "everything shows up at the root" (see [START_REF] Aldous | Processes on unimodular random networks[END_REF][Lemma 2.3]). Now, the same argument as in the above proof shows that

E deg S λ (o)1 (o∈S λ ) = 2E x∈∂o α o β x→o 1 (o∈S λ ) 1 (x∈S λ ) ≤ 2E x∈∂o α o β x→o 1 (o∈S λ ) = 2E (1 -α o ) 1 (o∈S λ ) ,
where in the last line, we have used (33). Consequently, if P(o ∈ S λ ) > 0, then

E deg S λ (o) o ∈ S λ < 2.
Inview of Theorem 11, this strict inequality contradicts the fact that all components of S λ are infinite with probability 1. Thus, we must have P(o ∈ S λ ) = 0, as desired.

The alternative formulation [START_REF] Cvetković | Spectra of graphs[END_REF]. Let us now rewrite the main formula (13) into the component form ( 14) using the fact that the components of S λ are finite trees. If x, y are neighbors and both lie in S λ , define the mass sent from x to y to be |K |/|K|, where K is the connected component of S λ containing x and y, and K is the restriction of K to those vertices that are closer to x than to y. Otherwise, the mass sent is zero. The Mass Transport Principle then reads

E 1 - 1 |C(S λ , o)| 1 (o∈S λ ) = E deg S λ (o) -1 + 1 |C(S λ , o)| 1 (o∈S λ ) .
Rearranging, we see that

P (o ∈ S λ ) - 1 2 E deg S λ (o)1 (o∈S λ ) = E 1 (o∈S λ ) |C(S λ , o)| . (45)
Now, let us define another mass transport: the mass sent from any x to any y is 1/(|C(S λ , y)| deg S λ (x)) if y ∈ S λ and x ∈ ∂C(S λ , y), and zero otherwise. Then the Mass Transport Principle reads

E   1 (o∈S λ ) |C(S λ , o)| x∈∂C(S λ ,o) 1 deg S λ (x)   = P (o ∈ ∂S λ ) .
Combining those two identities shows that the main formula ( 13) is indeed equivalent to [START_REF] Cvetković | Spectra of graphs[END_REF].

λ-primality of the connected components. Take a self-adjoint tree T = (V, E), and consider any finite connected component S of the subgraph induced by S λ . By (34),

γ y→x = 1 γ x→y ,
for any internal edge {x, y} in S. This implies that we may write

γ y→x = -φ(y) φ(x) ,
for some function φ : S → R \ {0} (unique, up to proportionality). On the other hand, the identities (34) and (36) together ensure that for any x ∈ S,

- y∈∂x∩S γ y→x = λ.
Those two equations together show that φ is a (non-vanishing) eigenfunction of S associated with the eigenvalue λ. This is enough to conclude, thanks to the following characterization.

Lemma 12. Let λ ∈ R and let T be a finite tree. Then the following are equivalent:

(i) T admits a nowhere-vanishing eigenfunction for the eigenvalue λ.

(ii) T is λ-prime, i.e., λ is an eigenvalue of T but not of T \ o, for any o ∈ V .

Proof. The implication (ii) =⇒ (i) is easy and actually holds for arbitrary graphs, as already noted below the definition of λ-primality. We focus on the converse. Fix a finite tree T = (V, E) and a function φ :

V → R \ {0} satisfying, at every x ∈ V , y∈∂x φ(y) = λφ(x) (46)
Now, consider an oriented edge (o, o ) and a function ϕ : V → R and suppose that ϕ satisfies (46) at every vertex x of T o→o , except maybe at x = o. We claim that the restriction ϕ T o→o is then proportional to φ T o→o . Let us prove this by induction on the height of the tree T o→o . If it is reduced to its root o, then the claim is trivial. Now, inductively, assume that the claim holds for the trees T x 1 →o , . . . , T x d →o , where x 1 , . . . , x d are the neighbors of o other than o . This means that there exists proportionality constants κ 1 , . . . , κ d such that ϕ Tx i →o = κ i φ Tx i →o for each 1 ≤ i ≤ d.

Comparing the eigenvalue equation for ϕ and for κ i φ at x = x i , we immediately deduce that

ϕ(o) = κ i φ(o). (47)
Since φ(o) = 0, we conclude that κ

1 = • • • = κ d = ϕ(o) φ(o)
, and this precisely means that ϕ T o→o is proportional to φ T o→o , as desired. We now have all we need to prove (ii): fix o ∈ V and suppose that T \ o admits an eigenfunction ϕ associated with the eigenvalue λ. Extend it to a function on V by setting ϕ(o) = 0. Then ϕ satisfies (46) at every x ∈ V \ o, and the above argument shows that it must be proportional to φ everywhere on V . Since φ(o) = 0, this forces ϕ ≡ 0, as desired.

Proof of Theorem 6

We split the proof into two parts: Lemma 13 converts the presence of spectral atoms with high tree-complexity into the existence of certain thin sets in the tree. In turn, Lemma 14 shows that the presence of such thin sets forces the anchored isoperimetric constant of the tree to be small. Lemma 13. Let L be a unimodular network concentrated on trees with all degrees in {2, . . . , ∆}, and let λ ∈ Σ p.p. (L). Set ε = 2(∆-2) τ (λ) . Then S := S λ ∪ ∂S λ is ε-thin in the following sense: (i) S has positive density, i.e. P (o ∈ S) > 0. We note that the construction of S may use some external randomization; the crucial point is that the resulting network (with S encoded as vertex marks) is unimodular, so that the above use of the Mass Transport Principe remains valid. Note that S is ε -thin with ε = 3∆ε 2 since by construction We may thus apply the first part of the proof with (S , ε ) instead of (S, ε), and the claim follows.

Figure 1 :

 1 Figure 1: Left: histogram of the eigenvalues of a uniform 3-regular random graph on n = 10 4 vertices (in gray), compared with the Kesten McKay density (3) (in red). Right: histogram of the eigenvalues of the Erdős-Rényi random graph with n = 10 4 , p = 2/n. One of the main motivations for our work is to relate this striking difference of regularity to the geometry of the graphs.

( 1 P

 1 ii) The subgraph induced by S has minimum degree at least two, i.e. P (deg S (o) ≥ 2 | o ∈ S) = 1. (iii) Vertices in S have total degree (in the orginal tree) close to two, i.e. E [deg(o) -2 | o ∈ S] ≤ ε.Proof. The condition (i) is clear, since λ ∈ Σ p.p (L). The condition (ii) follows from Lemma 10 when o ∈ ∂S λ , and from the assumption on L when o ∈ S λ . We now focus on (iii). If each x ∈ S λ sends mass 1 to each y ∈ ∂x \ S λ , then the Mass Transport Principle readsE deg ∂S λ (o)1 (o∈S λ ) = E deg S λ (o)1 (o∈∂S λ ) .On the other hand, recall from equation (45) thatE deg S λ (o) -2 1 (o∈S λ ) = -2E 1 (o∈S λ ) |C(S λ , o)| ,and from the identities (13) and (45) thatP (o ∈ ∂S λ ) = E 1 (o∈S λ ) |C(S λ , o)| -µ L ({λ}).Combining those three identities, we arrive atE (deg(o) -2) 1 (o∈S) = E deg(o) + deg S λ (o) -2 1 (o∈∂S λ ) -2E 1 (o∈S λ ) |C(S λ , o)| ≤ 2(∆ -2)E 1 (o∈S λ ) |C(S λ , o)| ≤ 2(∆ -2) τ (λ) P (o ∈ S) ,which is exactly the claim (iii).Lemma 14. Let L be a unimodular network concentrated on trees with degrees in {2, . . . , ∆}. Suppose that it admits an ε-thin set in the sense of Lemma 13 above. Then the event(G, o) ∈ G : i (G, o) ≤ 3∆ε 2has positive probability under L.Proof. We first work under the extra assumption that the ε-thin set S achieves equality in condition (ii), i.e., the subgraph induced by S is a disjoint union of bi-infinite paths (called a line ensemble in[START_REF] Bordenave | Mean quantum percolation[END_REF]). On the event {o ∈ S}, let S n ⊆ S denote the subpath consisting of the 2n + 1 vertices of S that lie within distance n from o, and define a mass transport by letting o send mass deg(o) -2 to every vertex in S n . Then the Mass Transport Principle reads as follows:E 1 (o∈S) x∈Sn (deg(x) -2) = (2n + 1)E 1 (o∈S) (deg(o) -2) .Now, the sum on the left-hand side is exactly |∂S n | -2, while the expectation on the right-hand side is at most εP (o ∈ S), by definition of ε-thinness. Rearranging, we arrive atE 1 (o∈S) (o ∈ S) .On the other hand, on {o ∈ S}, we have by definition of the anchored isoperimetric constant, i (G, o) ≤ lim inf n→∞ |∂S n | |S n | . By Fatou's Lemma, we conclude that E i (G, o)1 (o∈S) ≤ ε P (o ∈ S) , so that the event {(G, o) ∈ G : i (G, o) ≤ ε} has positive probability under L. In the general case, we may always "extract" from S a random subset S with internal degree exactly 2 in a unimodular way, thanks to [12, Proposition 5.4] (we actually apply this Proposition to the unimodular law L obtained from L by conditioning on o ∈ S and restricting the graph to C(S, o), with marks on the vertices to keep track of their degrees in the original graph). The resulting set S ⊆ S satisfies (i) P (o ∈ S ) ≥ 2 3∆ P (o ∈ S); (ii) P [deg S (o) | o ∈ S ) = 1.

E

  [(deg(o) -2)1 o∈S ] ≤ E [(deg(o) -2)1 o∈S ] ≤ εP (o ∈ S) ≤ 3∆ε 2 P o ∈ S .