# Spectral gap and embedded trees for the Laplacian of the Erdős-Rényi graph

Raphael Ducatez, Renaud Rivier

► To cite this version:

Raphael Ducatez, Renaud Rivier. Spectral gap and embedded trees for the Laplacian of the Erdős-Rényi graph. 2023. hal-04784816

HAL Id: hal-04784816

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

Preprint submitted on 15 Nov 2024

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
Spectral gap and embedded trees for the
Laplacian of the Erdős-Rényi graph

Raphael Ducatez* and Renaud Rivier†

October 2, 2023

Abstract

For the Erdős-Rényi graph of size N with mean degree $(1+o(1))^{\frac{\log N}{t+1}} \le d \le (1-o(1))^{\frac{\log N}{t}}$ where $t \in \mathbb{N}^*$, with high probability the smallest non zero eigenvalue of the Laplacian is equal to $2 - 2\cos(\pi(2t+1)^{-1}) + o(1)$. This eigenvalue arises from a small subgraph isomorphic to a line of size $t$ linked to the giant connected component by only one edge.

# 1 Introduction

## 1.1 Introduction

The Erdős-Rényi graph is the most natural and simple model for random graph [ER60]: from the complete graph with $N$ vertices, every edge is kept with probability $p = p_N$ independently. The asymptotic behavior has been extensively studied [BB98, JRL11] for various regimes of $p_N$ and has shown a large number of phenomena, for example, the apparition of a component of macroscopic size at $p_N > \frac{1}{N}$ or the connectivity of the graph for $p_N > \frac{\log N}{N}$.

Together with the adjacency matrix, the Laplacian is a canonical way to encode the structure of the graph. It appears in physics as the Hamiltonian of a quantum particle living on the graph or, in probability, as the generator associated with the random walk on the graph. Spectral analysis of the Laplacian of the Erdos-Reyni has recently enjoyed new results. The bulk of the spectrum has been analyzed in [HL20] down to polynomial regimes and to $d \ge \sqrt{\log N}$ in [Riv23, Chapter 2] where local laws down to optimal scale were shown for the Green function. In particular, in the supercritical regime, $d \ge \log N$ the law of the spectrum in the bulk can be characterized by the free-convolution between a Gaussian law (coming from the diagonal matrix of the degree) and a semi-circle law (coming from the adjacency matrix). The right edge of the spectrum has been studied in [Riv23, Chapter 3] where the author showed that the largest eigenvalues are matched with the largest degrees in the graph (see also

<footnote>*Université Claude-Bernard Lyon 1</footnote>

<footnote>†Université de Genève</footnote>
[CLO+22]). In a series of papers [ADK21a, ADK21b, ADK21c] the authors had previously achieved similar results for the adjacency matrix. For the left edge of the spectrum of the Laplacian in the supercritical regime $d \ge \log N$ a correspondence can be established between the smallest eigenvalues and small-degree vertices (see [Riv23, Chapter 3])

In this paper, we study the spectrum of the Laplacian for subcritical regimes $d \le \log N$ and compute its smallest non-zero eigenvalue $\lambda_2$ also called the spectral gap. Contrarily to the supercritical regime, for $d \le \log N$ the graph becomes disconnected and small connected components begin to appear. We recall that the Laplacian is a positive matrix with $\lambda_1 = 0$ whose multiplicity is equal to the number of connected components. A natural guess would be that $\lambda_2$ is obtained from the Laplacian restricted to the small disconnected clusters. We prove that the smallest eigenvalues are created by small clusters connected to the giant connected component by only one edge. Moreover among all these small clusters, the line of maximal length is the optimal subgraph to minimize the eigenvalue. We then obtain an explicit formula $\lambda_2 = 2 - 2 \cos(\pi(2t_* + 1)^{-1}) + o(1)$ with $t_* \in \mathbb{N}^*$ corresponding to the size of the largest but non-giant disconnected component.

## 1.2 Model

For $G = (V, E)$ a graph with $V$ the set of vertices and $E$ the set of edges we denote $L(G) \in \mathbb{R}^{|V| \times |V|}$ the Laplacian, $A(G) \in \mathbb{R}^{|V| \times |V|}$ the adjacency matrix and $D(G) \in \mathbb{R}^{|V| \times |V|}$ the diagonal matrix of the degree associated with the graph defined by

$$L(G) = \sum_{e \in E} L(e), \quad A(G) = \sum_{e \in E} A(e), \quad L(G) = D(G) - A(G)$$

where for every $e = (x, y) \in V^2$

$$L(e) := L((x, y)) = (1_x - 1_y)(1_x - 1_y)^*, \quad A(e) := A((x, y)) = 1_x 1_y^* + 1_y 1_x^*.$$

We consider the Erdős-Rényi graph $G_{N,d_N}$ defined with set of vertices $V = \{1, \dots, N\}$ and set of edges $E$ where each $(x, y) \in V^2$, $x \ne y$ is added to the graph at random, independently and with probability $p_N = d_N/N$. We call $d_N$ the mean degree of $G_{N,d_N}$.

We say that $\Omega = (\Omega_N)_{N \in \mathbb{N}}$, events on the Erdős-Rényi graph of size $N$, occurs with high probability if $\mathbb{P}(\Omega_N) \to 1$ as $N \to \infty$.

## 1.3 Main results

We are interested in the first non-zero eigenvalue of the Laplacian that we denote

$$\lambda_2 := \min(\text{Spec}(L(G_{N,d_N}))) \setminus \{0\}).$$

Here is our main result.
**Theorem 1.1.** Let $t_* \in \mathbb{N}^*$, $\epsilon > 0$ and $d_N$ such that

$$ (1 + \epsilon) \frac{\log N}{t_* + 1} \le d_N \le (1 - \epsilon) \frac{\log N}{t_*}. \qquad (1) $$

As $N \to \infty$ with high probability, we have

$$ \lambda_2 = 2 - 2 \cos \left( \frac{\pi}{2t_* + 1} \right) + O \left( \frac{1}{\log N} \right). \qquad (2) $$

As we will see in the proof, the value of $\lambda_2$ is closely linked with the existence of lines of length $t_*$ that are connected to the rest of the graph by exactly one edge. The picture below summarizes the various regimes covered.

<figure><img src="image_2.png" /><figcaption>Figure 1: Illustration of the regimes covered by Theorem 1.1. As the density parameter $d$ decreases, the graph becomes sparser and longer lines appear. Some of those lines are connected by exactly one edge to the main connected component and generate the formula_2(2) for $\lambda_2$. The regimes corresponding to $d \ge \log N$ (small degree vertices) are not covered in this paper but a detailed analysis can be found in [Riv23, Chapter 3].</figcaption></figure>

# 2 Proof of Theorem 1.1

## 2.1 Notations

In the rest of the paper we simply write $\mathbb{G} = \mathbb{G}_{N,p_N}$ and $d = d_N$. We recall that a multiset is a set where elements can appear multiple times. We use the notation $\tilde{X}$ for a multiset, $X$ for the associated set and for $x \in X$ we write $\tilde{X}(x)$ the multiplicity of $x$. For example with $\tilde{X} = \{x, x, y\}$ we have $X = \{x, y\}$. $\tilde{X}(x) = 2$, $\tilde{X}(y) = 1$. We also denote $\tilde{X} \subset [[Y]]$ for $X \subset Y$.

**Definition 2.1.** For a graph $G = (V, E)$ and subgraph $T \subset V$ we define the anchor $\tilde{\partial}T$ as the multiset

$$ \tilde{\partial}T = \{x \in T: (x, y) \in E, y \notin T\} $$

It corresponds to the *outgoing degree* of the vertices of $T$.
**Definition 2.2.** For a graph $G = (V, E)$ and a multiset $\hat{X} \subset [[V]]$ we define the weighted Laplacian

$$L(G; \hat{X}) = L(G) + \sum_{x \in \hat{X}} 1_x 1_x^* = L(G) + \sum_{x \in X} \hat{X}(x) 1_x 1_x^*.$$

*Remark 2.3.* Given $T \subset V$, the weighted Laplacian corresponds to the usual matrix restriction, $L(T; \widehat{\partial T}) = L(G)|_T$.

## 2.2 Proof of Theorem 1.1

Through all the paper $t_* \in \mathbb{N}^*$, $\epsilon \in (0, \frac{1}{4})$ and as $-\tau \log \tau + \tau \to 0$ for $\tau \to 0$ we can choose $\tau \in (0, 1)$ small enough such that

$$-\tau \log \tau + \tau \le \frac{\epsilon}{2}. \qquad (3)$$

Define

$$\mathcal{V} = \{x \in [N], D_x \le \tau d\}.$$

We call a line of size $t \in \mathbb{N}$ the graph

$$\mathbb{L}_t = (\{1, \dots, t\}, E) \text{ with } E = \{(i, i+1): 1 \le i < t\}$$

**Proposition 2.4.** With high probability

1. $G|_V$ is a forest.

2. For any tree $T \subset G|_V$ we have $|T| \le t_*$.

3. There exists a tree $T \subset G|_V$ that is isomorph to a line of size $t_*$ and such that it is connected to $(\mathcal{V})^c$ by exactly one edge attached at one of its two extremal points.

Denote $\mathfrak{F}$ the set of tree in the forest $G|_V$.

**Proposition 2.5.** With high probability

$$\sum_{\lambda \in \text{Spec}(L(\mathbb{G}))} \delta_{\lambda}, \quad \text{and} \quad \delta_0 + \sum_{T \in \mathfrak{F}} \sum_{\mu \in \text{Spec}(L(T; \widehat{\partial T}))} \delta_{\mu + \epsilon_{\mu}}$$

agree on the interval $[0, \frac{1}{2}\tau d]$ and such that $\epsilon_{\mu} = O((1+\mu)d^{-1})$ for all $\mu$.

**Proposition 2.6.** For any tree $T$ of size $|T| \le t_*$, $\hat{X} \subset [[T]]$ and $\mu \in \text{Spec}(L(T; \hat{X}))$ with $\mu > 0$ we have

$$\mu \ge 2 - 2 \cos \left( \frac{\pi}{2t_* + 1} \right). \qquad (4)$$

Moreover equality holds if and only if $T$ is a line of size $t_*$ and $\hat{X}$ one of its extremal point and $\mu$ its smallest eigenvalue.
We prove Proposition 2.4 in Section 3, Proposition 2.5 in Section 4 and Proposition 2.6 in Section 5. We then deduce Theorem 1.1 from these Propositions.

*Proof of Theorem 1.1.* Because of Proposition 2.5 it is enough to study the spectrum of Spec($L(T; \partial \hat{T})$) with $T \in \mathfrak{F}$ and $\partial \hat{T}$ the associated anchor. Using item 2 of Proposition 2.4 and Equation (4) of Proposition 2.6 we obtain that with high probability

$$ \lambda_2 \geq 2 - 2 \cos \left( \frac{\pi}{2t_* + 1} \right) + O(d^{-1}). $$

On the other hand using item 3 of Proposition 2.4 and the equality case of Proposition 2.6 we also have that with high probability

$$ \lambda_2 \leq 2 - 2 \cos \left( \frac{\pi}{2t_* + 1} \right) + O(d^{-1}). $$

□

## 3 Probability estimate on the graph, proof of Proposition 2.4

This section is about properties of the random graph that occur with high probability and that we use in the following sections. Let us begin this section by setting a few notations. We equip the graph $\mathbb{G}$ with its natural graph distance $\text{dist}_{\mathbb{G}}$. For $x \in [N]$ and $i \in \mathbb{N}$, we define the sphere of radius $i$ around $x$ as

$$ S_i(x) := \{y \in [N] : \text{dist}_{\mathbb{G}}(x, y) = i\}, $$

as well as the balls of radius $i$ around $x$, $B_i(x) := \bigcup_{j \leq i} S_j(x)$.

**Lemma 3.1.** With high probability, there exists a unique giant connected component $\mathbb{G}_{cc}$ with size $N(1 - o(1))$. Moreover $\mathbb{G}_{cc}^c \subset \mathcal{V}$.

*Proof.* The giant connected component is a very classical result, see for example [BB98]. Also because [BB98, Theorem 6.10] all the small connected component are of size $O(1)$, than every very vertices of degree at least $\tau d$ belongs to $\mathbb{G}_{cc}$. □

We now state a few results from [ADK21b].

**Proposition 3.2.** For some $C > 0$ and $r < \frac{\epsilon \log N}{4(1+t_*)^2 \log d}$ with high probability, we have

1. $\forall x \in [N], D_x \leq Cd,$

2. $\|A(\mathbb{G}) - E(A(\mathbb{G}))\| \leq C\sqrt{d}$

3. $|V| \leq N^{1-\frac{1}{1+t_*}},$
4. For all $x \in \mathcal{V}$, $\mathbb{G}|_{B_r(x)}$ is a tree,

5. For all $x \in \mathcal{V}$, $|B_r(x) \cap \mathcal{V}| \le t_*.

*Proof of Proposition 3.2.* Item 1 is stated in [ADK21b, Lemma 3.3] and Item 2 is stated in [ADK21b, Corollary 2.3]. We now prove Item 3. We can apply [ADK21b, Lemma D.2]] with $n = N - 1$ and $\mu = d(1 - N^{-1})$ and $a = \tau - 1 + O(N^{-1})$, we find

$$ \mathbb{P}(x \in \mathcal{V}) \le e^{-d(\tau \log \tau - \tau + 1)}(1+O(N^{-1})) \le N^{-\frac{1+\epsilon}{1+t_*}(1-\frac{\epsilon}{2})}(1+O(N^{-1})) = O(N^{-\nu}), \quad (5) $$

where we chose $\tau$ as in 3 and $\frac{(1+\epsilon)(1-\epsilon/2)}{1+t_*} \ge \nu \ge \frac{1+\epsilon/3}{1+t_*}$, for $\epsilon \le 1/3$. We find that for a $C \ge 0$ large enough

$$ \mathbb{E}|\mathcal{V}| = N\mathbb{P}(x \in \mathcal{V}) \le CN^{1-\nu} $$

so that by Markov $\mathbb{P}(|\mathcal{V}| \ge N^{1-\frac{1}{1+t_*}}) \le CN^{\frac{1}{1+t_*}-\nu} = O(N^{-\frac{\epsilon}{3(1+t_*)}})$.

To prove Item 4 we use [ADK21b, Lemma 5.5] with $k = 1$ and have that for any $x \in [N]$,

$$ \mathbb{P}(x \in \mathcal{V}, B_r(x) \text{ contain a cycle}) \le 2r^2(Cd)^{2r+1}N^{-1-\frac{1}{t_*+1}} = o(N^{-1}), $$

where we use that $(2r + 1) \log d + 2 \log r \le 4r \log d \le \frac{4\epsilon \log N}{(1+t_*)^2} \le \frac{4}{5(t_*+1)} \log N$. Using a union bound, we conclude that

$$ \mathbb{P}(\exists x \in [N], x \in \mathcal{V}, B_r(x) \text{ contain a cycle}) = o(1). $$

To prove Item 5 we explore the neighbourhood of $x$ adding the set $S_i(x)$ for $i \le r$ one after the other. We denote the set of edges

$$ E_{i+1} = E(\mathbb{G}(B_{i+1})) \setminus E(\mathbb{G}(B_i)) \cup E(\mathbb{G}(S_i)) $$

and the generated sigma algebra $\mathcal{F}_i = \sigma(E_1, \dots, E_i)$. This corresponds to $\mathbb{G}(B_i)$ without the set of edges $\{(x, y) \in E : x, y \in S_i\}$. Remark that conditionally on $\mathcal{F}_i$, $E_{i+1}$ is given by a set of $|S_i| \times (N - |B_i|)$ independent random Bernoulli variables of parameter $\frac{d}{N}$.

For $y \in S_i$, we define the random variables $\tilde{D}_y := |S_1(y) \cap S_{i+1}|$ which form a family of independent random variable with $\tilde{D}_y \le D_y - 1$. We introduce $V_i = |S_i \cap \mathcal{V}|$ and, using (5), we find that, for any $m_1, \dots, m_r \in \mathbb{N}$,

$$ \begin{aligned} 1_{|S_i| \le (Cd)^i} \mathbb{P}(V_i \ge m_i | \mathcal{F}_i) &\le 1_{|S_i| \le (Cd)^i} \sum_{\{y_1, \dots, y_{m_i}\} \subset S_i} \mathbb{P}(\cap_{j \le m_i} \{\tilde{D}_{y_j} \le \tau d - 1\} | \mathcal{F}_i) \\ &\le (Cd)^{im_i} N^{-m_i \nu}. \end{aligned} $$
We denote $\mathcal{D}(m) = \{(m_i) \in \mathbb{N}^r : \sum_{i=1}^r m_i = m\}$ and we have

$$ 
\begin{aligned}
1_{\forall y \in B_r(x), D_y \le C d} \mathbb{P}(|B_r(x) \cap \mathcal{V}| \ge m | \mathcal{F}_r) &\le 1_{\forall y \in B_r(x), D_y \le C d} \sum_{\mathcal{D}(m)} \mathbb{P}(\cap_{i=1}^r \{V_i \ge m_i\} | \mathcal{F}_r) \\
&\le \sum_{\mathcal{D}(m)} \prod_{i=1}^r 1_{|S_i| \le (Cd)^i} \mathbb{P}(V_i \ge m_i | \mathcal{F}_i) \\
&\le r^m (Cd)^{rm} N^{-m\nu}
\end{aligned}
$$

Therefore for $m = t_* + 1$ we have $N^{-m\nu} \le N^{-(1+\frac{\epsilon}{3})}$ and then

$$ \mathbb{P}(\forall y \in [N], D_y \le C d \cap |B_r(x) \cap \mathcal{V}| \ge t_*+1) \le r^{t_*+1} (Cd)^{r(t_*+1)} N^{-(1+\frac{\epsilon}{3})} = o(N^{-1}) $$

where we use that $(1+t_*)r \log d < \frac{\epsilon \log N}{4(1+t_*)}$. Using a union bound, we conclude that

$$ \mathbb{P}(\exists x \in [N], |B_r(x) \cap \mathcal{V}| \ge t_* + 1) = o(1). $$

□

With Proposition 3.2 we obtain the two first items of Proposition 2.4. We now prove the last item.

**Proof of Proposition 2.4, item 3.** We denote $\mathcal{N}$ the number of tree $T \subset \mathbb{G}|_{\mathcal{V}}$ that is isomorph to a line of size $t_*$ and such that it is connected to $\mathcal{V}^c$ by exactly one edge attached at one of its extremal point. We use a second-moment method and will prove that

$$ 
\begin{aligned}
\mathbb{E}(\mathcal{N}) &= Nd^{t_*}e^{-t_*d} \left(1 + O\left(\frac{t_*^2d}{N}\right)\right) \\
\mathbb{E}(\mathcal{N}^2) - \mathbb{E}(\mathcal{N})^2 &= O\left(\mathbb{E}(\mathcal{N}) + 1 + \frac{t_*^2d\mathbb{E}(\mathcal{N})^2}{N}\right) \quad (6)
\end{aligned}
$$

Assuming Equation (6) we have $\mathbb{E}(\mathcal{N}) \ge N^{1-(1-\epsilon)\frac{t_*}{N}+o(1)} \to \infty$ where we use (1) and then by Chebyshev's inequality

$$ \mathbb{P}(\mathcal{N} = 0) \le \mathbb{P}\left(\mathcal{N} \le \frac{\mathbb{E}(\mathcal{N})}{2}\right) \le \frac{4\mathbb{E}(\mathcal{N} - \mathbb{E}\mathcal{N})^2}{\mathbb{E}(\mathcal{N})^2} = \mathbb{O}\left(\frac{1}{\mathbb{E}(\mathcal{N})}\right) = o(1). $$

We now prove Equation (6). For $Y = \{y_1, \dots, y_{t_*}, x\} \subset [N]$, $\mathcal{L}_Y$ the event that $\mathbb{G}|_{\{y_1, \dots, y_{t_*}\}}$ is a line and that $(y_{t_*}, x)$ is the only edge between $\{y_1, \dots, y_{t_*}\}$ and $\{y_1, \dots, y_{t_*}\}^c$. Then

$$ \mathbb{P}(\mathcal{L}_Y) = \frac{d^{t_*}}{N^{t_*}} \left(1 - \frac{d}{N}\right)^{t_* (N - t_*) + 1} = \frac{d^{t_*}}{N^{t_*}} e^{-dt_*} \left(1 + O\left(\frac{t_*^2 d}{N}\right)\right) $$

Then

$$ \mathbb{E}(\mathcal{N}) = \sum_Y \mathbb{P}(\mathcal{L}_Y) = Nd^{t_*}e^{-dt_*} \left(1 + O\left(\frac{t_*^2 d}{N}\right)\right). $$
We also have

$$ \mathbb{E}(\mathcal{N}^2) - \mathbb{E}(\mathcal{N})^2 = \sum_{Y_1, Y_2} \mathbb{P}(\mathcal{L}_{Y_1} \cap \mathcal{L}_{Y_2}) - \mathbb{P}(\mathcal{L}_{Y_1})\mathbb{P}(\mathcal{L}_{Y_2}) $$

If $Y_1$ and $Y_2$ are disjoint, the probability that there is no edges between $Y_1$ and $Y_2$ should be added only once and we have

$$ \mathbb{P}(\mathcal{L}_{Y_1} \cap \mathcal{L}_{Y_2}) = \mathbb{P}(\mathcal{L}_{Y_1})\mathbb{P}(\mathcal{L}_{Y_2})\left(1 - \frac{d}{N}\right)^{-t_*^2} $$

Therefore

$$ \sum_{Y_1, Y_2, \text{disjoint}} \mathbb{P}(\mathcal{L}_{Y_1} \cap \mathcal{L}_{Y_2}) - \mathbb{P}(\mathcal{L}_{Y_1})\mathbb{P}(\mathcal{L}_{Y_2}) = O\left(\frac{dt_*^2}{N}\mathbb{E}(\mathcal{N})^2\right) $$

If $Y_1 \cap Y_2 \neq \emptyset$ and $Y_1 \neq Y_2$ we have that then $Y_1 \cup Y_2$ form a connected component in $\mathcal{V}$ and then

$$ \sum_{Y_1 \neq Y_2, Y_1 \cap Y_2 \neq \emptyset} \mathbb{P}(\mathcal{L}_{Y_1} \cap \mathcal{L}_{Y_2}) \leq t_*^2 \mathbb{E}(|\{U \text{ connected component in } \mathcal{V}, |U| \geq t_* + 1\}|) \\ = o(1), $$

as in the proof of Item 5 of Proposition 3.2. Finally for the case $Y_1 \cap Y_2 \neq \emptyset$ and $Y_1 = Y_2$ we just have

$$ \sum_{Y_1, Y_2, Y_1=Y_2} \mathbb{P}(\mathcal{L}_{Y_1} \cap \mathcal{L}_{Y_2}) = \mathbb{E}(\mathcal{N}). $$

and Equation (6) follows from the three above estimates. $\square$

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

# 4 Rigidity results, proof of Proposition 2.5

We analyze the spectrum of the graph locally around the vertices in $\mathcal{V}$. We will work on small clusters of such vertices. Let us start by setting a few notations. For $M := (M_{xy})_{x,y \in [n]} \in \mathbb{R}^{n \times n}$ and $Y \subseteq [n]$ we denote by $M|_Y = (M_{xy})_{x,y \in Y}$ the restriction of $M$ to $Y$. We write $\lambda_1(M) \leq \lambda_2(M) \leq \dots \leq \lambda_n(M)$ the increasing ordering of the eigenvalues of $M$. We use the standard $\ell^2$ norm, $\| \cdot \| := \| \cdot \|_2$.

**Definition 4.1.** We denote $\mathfrak{A}$ the connected components of $\cup_{x \in \mathcal{V}} B_2(x)$.

We define some good properties of the graph.

**Definition 4.2.** Let $\Xi_1$ a probability set such that

1. For $x \in [N]$, $D_x \leq \mathcal{C}d$.

2. For all $U \in \mathfrak{A}$, $|\mathcal{V} \cap U| \leq t_*$.
3. The graph restricted to $\cup_{x \in V} B_3(x)$ is a forest.

Let $\Xi_2$ a probability set such that

1. For $x \in [N]$, $D_x \le C d$.

2. $\|A(\mathbb{G}) - E(A(\mathbb{G}))\| \le C\sqrt{d}$

3. $|V| \le N^{1-1/(1+t_*)}$,

These properties occur with high probability and we will assume that they are satisfied throughout this section.

**Proposition 4.3.** $P(\Xi_1 \cap \Xi_2) \ge 1 - o(1)$

*Proof of Proposition 4.3.* If $U$ is a cluster with $t_*+1$ vertices in $V$, then there is a chain $y_1, \cdots, y_{t_*+1} \in V$ such that for any $1 < i \le t_*+1$, there exists $j < i$ with $\text{dist}_{\mathbb{G}}(y_i, y_j) \le 5$. Therefore $y_j \in B_{y_1}(5t_*)$ for all $j \le t_*+1$ and we conclude that the probability is small by Proposition 3.2, item 5. The other items in $\Xi_1$ and $\Xi_2$ also follow from Proposition 3.2. $\square$

**Proposition 4.4.** On the event $\Xi_1$, for any $U \in \mathcal{U}$ and $F = V \cap U$,

$$ \sum_{\lambda \in \text{Spec}(L(\mathbb{G})|_U)} \delta_{\lambda}, \quad \text{and} \quad \sum_{\mu \in \text{Spec}(L(F; \widehat{\partial F}))} \delta_{\mu+\epsilon_{\mu}} $$

agree on the interval $[0, \frac{\tau}{2}d]$ and such that $\epsilon_{\mu} = O((\mu+1)d^{-1})$ for all $\mu$.

*Proof of Proposition 4.4.* Let us consider a connected component $U \in \mathcal{U}$ and the restriction of the Laplacian to this connected component $H := L(\mathbb{G})|_U$. Let $A := L(\mathbb{G})|_F$, $C := L(\mathbb{G})|_{U \setminus F}$ and $B \in \{0, -1\}^{|F| \times |U \setminus F|}$ such that

$$ H = \begin{pmatrix} A & B^* \\ B & C \end{pmatrix}. $$

Then recalling Definition 2.2, we see that $A = L(F, \widehat{\partial F})$. Note that $A$ may be itself a block matrix if $F$ is made up of disjoint trees. Moreover the matrix $C$ is given by the sum of a diagonal matrix with entries in the interval $[\tau d, +\infty)$ and the adjacency matrix of a forest with maximal degree $C d$ by item 3 of $\Xi_1$. By perturbation theory and Lemma 7.1 we know that

$$ \text{spec}C \subseteq [\tau d - 2\sqrt{C}d, \infty) \subseteq [3\tau d/4, \infty) \quad (7) $$

for $d$ large enough. In addition, since $B$ is given as the projection of the adjacency matrix of a collection of disjoint stars (rooted at vertices of $\partial F$), we know that $\|B\| \le \sqrt{\tau d}$.

We define

$$ H(s) = \begin{pmatrix} A & sB^* \\ sB & C \end{pmatrix} \quad \text{for } s \in [0, 1]. $$
Here $H(1) = H$ and $H(0)$ is block diagonal with the matrices $A$ and $C$ therefore $\text{spec}(H(0)) \cap [0, \frac{3}{4}\tau d) = \text{spec}(A) \cap [0, \frac{3}{4}\tau d)$. We write $\lambda_1(s) \le \lambda_2(s) \le \dots$ the eigenvalues of $H(s)$. By perturbation theory, these are Lipschitz functions. More precisely suppose $\lambda_i(s) \in \text{spec}(H(s)) \cap [0, \frac{\tau}{2}d]$, write $u(s) \in \mathbb{R}^{|U|}$ the corresponding normalized eigenvector and denote by $u_1(s) := u(s)|_F$ and $u_2(s) := u(s)|_{U \setminus F}$. We have

$$ \frac{d}{ds}\lambda_i(s) = \langle u(s), \left[ \frac{d}{ds}H(s) \right] u(s) \rangle = 2\langle u_1(s), B^*u_2(s) \rangle \quad (8) $$

where we use that $2\langle \frac{d}{ds}u(s), H(s)u(s) \rangle = \lambda(s)\frac{d}{ds}\|u(s)\|^2 = 0$. In the case of a degenerate eigenvalue, $u(s)$ is not well defined. However one can still choose a normalized vector in the eigenspace such that the above equation is true (following the classical proof that the eigenvalues are Lipschitz using min-max principle).

We will prove that

$$ \left| \frac{d}{ds} \lambda_i(s) \right| \le \frac{8t_*}{\tau d} (\lambda_i(s) + 4), \quad s \in [0, 1], \quad (9) $$

from which we will conclude that

$$ |\lambda - \mu| = |\lambda_i(0) - \lambda_i(1)| = O((\lambda_i(0) + 1)d^{-1}). $$

Recall here that $\lambda_i(0) \in \text{spec}(A) = \text{spec}(L(F; \widehat{\partial}F))$ and $\lambda_i(1) \in \text{spec}(L(\mathbb{G})|_U)$.

Let us fix $s \in [0, 1]$ and write $\lambda = \lambda(s)$ and $u_i = u_i(s)$ in the following computations. The eigenvalue-eigenvector equation can be written in blocks as

$$ \begin{pmatrix} A - \lambda & sB^* \\ sB & C - \lambda \end{pmatrix} \begin{pmatrix} u_1 \\ u_2 \end{pmatrix} = 0. $$

Using (7), $\|B\| \le \sqrt{\tau d}$ and standard perturbation theory, we see that

$$ \min_{\nu \in \text{spec}(C)} |\lambda - \nu| \ge \frac{\tau d}{4}. $$

The matrix $C - \lambda$ is thus invertible with $\|(C - \lambda)^{-1}\| \le \frac{\tau d}{4}$. After a couple of substitutions, the eigenvalue-eigenvector equation becomes

$$ \left\{ \begin{array}{l} u_2 = -s(C - \lambda)^{-1}Bu_1, \\ (A - s^2B^*(C - \lambda)^{-1}B)u_1 = \lambda u_1. \end{array} \right. \quad (10) $$

Replacing $A$ by the deformed Laplacian matrix and applying $u_1^*$ to the second line yields

$$ \lambda \|u_1\|^2 = \langle u_1, L(F)u_1 \rangle + \sum_{x \in \partial F} \widehat{\partial}F(x) u_1(x)^2 - s^2 \langle u_1, (B^*(C - \lambda)^{-1}B)u_1 \rangle. $$
and then

$$ \sum_{x \in \partial F} \widehat{\partial F}(x) u_1(x)^2 \le \lambda \|u_1\|^2 + s^2 |\langle u_1, (B^*(C-\lambda)^{-1}B)u_1 \rangle| \le (\lambda+4) \|u_1\|^2 \quad (11) $$

where we use the fact that $L(F)$ is positive and that $\|B^*(C - \lambda)^{-1}B\| \le \|B\|^2 \|(C - \lambda)^{-1}\| \le 4$. Finally, applying $\langle u_1^*, B^* \rangle$ to the first line of (10), we get

$$ \begin{aligned} |\langle u_1, B^* u_2 \rangle| &= |\langle u_1, B^*(C-\lambda)^{-1} B u_1 \rangle| \\ &= \left| \sum_{x,y \in \partial F} u_1(x) u_1(y) \langle B1_y, (C-\lambda)^{-1} B1_x \rangle \right| \\ &\le \sum_{x,y \in \partial F} |u_1(x)| |u_1(y)| \frac{4\sqrt{\widehat{\partial F}(x)\widehat{\partial F}(y)}}{\tau d} \\ &= \frac{4}{\tau d} \left( \sum_{x \in \partial F} |u_1(x)| \sqrt{\widehat{\partial F}(x)} \right)^2 \\ &\le \frac{4t_*}{\tau d} (\lambda+4) \|u_1\|^2. \end{aligned} $$

by Cauchy-Schwartz and (11). This proves (9) and concludes the proof. □

**Proposition 4.5.** On the event $\Xi_1$, for any $U \in \mathcal{U}$, $\lambda \in [0, \frac{\tau}{2}d] \cap \text{Spec}(L(\mathbb{G}|_U))$ and $u$ the associated eigenvector we have

$$ \|u\|_{\partial U} = O(d^{-1}) $$

*Proof of Proposition 4.5.* We use the same notation as for the proof of Proposition 4.4. Setting $s = 1$ in 4, we have

$$ u_2 = -(C - \lambda)^{-1} B u_1. $$

Let us write $C = D - A(\mathbb{G}|_{U \setminus F})$ with $D := D(\mathbb{G})|_{U \setminus F}$. The second resolvent identity reads

$$ (C - \lambda)^{-1} = (D - \lambda)^{-1} + (C - \lambda)^{-1} A(\mathbb{G}|_{U \setminus F}) (D - \lambda)^{-1}, $$

and because $\text{supp}((D - \lambda)^{-1} B u_1) \subset \cup_{x \in F} S_1(x)$, we have

$$ \text{supp}((D - \lambda)^{-1} B u_1 \cap \partial U) = \emptyset. $$

We thus find that

$$ u_2|_{\partial U} = - ((C - \lambda)^{-1} A(\mathbb{G}|_{U \setminus F}) (D - \lambda)^{-1} B u_1) |_{\partial U} $$
The graph $\mathbb{G}|_{U\setminus F}$ is a tree so by Lemma 7.1, we have $\|A(\mathbb{G}|_{U\setminus F})\| \le 2\sqrt{Cd}$. We can use the same bounds for $\|B\|$, $\|(D-\lambda)^{-1}\|$ and $\|(C-\lambda)^{-1}\|$ as in the proof of Proposition 4.4. Putting everything together, we find

$$ \|\mathbf{u}|_{\partial U}\| = \|u_2|_{\partial U}\| \le \frac{16\sqrt{C}}{\tau^{3/2}d} \|u_1\|. $$

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

**Proposition 4.6.** On the event $\Xi_2$, the vector $\mathbf{q} := \frac{1}{\sqrt{|Y|}}1_Y$, where $Y := [N]\setminus \bigcup_{x \in \mathcal{V}} B_3(x)$ satisfies for any $c < \frac{1}{1+t_*}$

$$ \|\mathbf{e} - \mathbf{q}\|^2 = O(N^{-c}), \quad \langle \mathbf{q}, L(\mathbb{G})\mathbf{q} \rangle = O(N^{-c}). $$

*Proof of Proposition 4.6.* On the event $\Xi_2$, we have

$$ |Y^c| \le \left| \bigcup_{x \in \mathcal{V}} B_3(x) \right| \le (Cd)^3 |\mathcal{V}| \le C^5 d^4 N^{1-\frac{1}{1+t_*}} = O(N^{1-c}), $$

for $c < \frac{1}{1+t_*}$. In particular, $|Y| = (1-o(1))N$. It is a straightforward computation to see that on $\Xi_1$

$$ \langle \mathbf{q}, L\mathbf{q} \rangle = \frac{1}{|Y|} \sum_{y \in \bigcup_{x \in \mathcal{V}} S_4(x)} 1 \le \frac{Cd|Y^c|}{|Y|} = O(N^{-c}), $$

and

$$ \mathbf{e} - \mathbf{q} = \frac{1}{\sqrt{N}} \sum_{y \notin Y} 1_y + \sum_{z \in Y} \left( \frac{1}{\sqrt{N}} - \frac{1}{\sqrt{|Y|}} \right) 1_z, $$

and thus

$$ \|\mathbf{e} - \mathbf{q}\|^2 = \frac{|Y^c|}{N} + \frac{(\sqrt{|Y|} - \sqrt{N})^2}{N} = O(N^{-c}). $$

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

**Proposition 4.7.** On the event $\Xi_2$, $\text{spec}(L(\mathbb{G})|_{\mathcal{V}^c}) \subset \{\mu\} \cup [\tau d/2, +\infty)$ for some $\mu = O(N^{-c})$, $0 < c < \frac{1}{1+t_*}$.

*Proof of Proposition 4.7.* We have

$$ L(\mathbb{G}) = D(\mathbb{G}) - (A(\mathbb{G}) - \mathbb{E}(A(\mathbb{G}))) - \mathbb{E}(A(\mathbb{G})). $$

By definition of $D$ and $\mathcal{V}$ we have $\lambda_1(D(\mathbb{G})|_{\mathcal{V}}) \ge \tau d$ and with Definition 4.2 we have that $\|A(\mathbb{G}) - \mathbb{E}(A(\mathbb{G}))\| = O(\sqrt{d})$. Therefore,

$$ \lambda_1((D(\mathbb{G}) - (A(\mathbb{G}) - \mathbb{E}(A(\mathbb{G}))))|_{\mathcal{V}^c}) \ge \tau d - O(\sqrt{d}). $$

Because $\mathbb{E}(A(\mathbb{G}))|_{\mathcal{V}^c} = \frac{d}{N}1_{\mathcal{V}^c}1_{\mathcal{V}^c}$ is a rank one matrix, by interlacing $\lambda_2(L(\mathbb{G})|_{\mathcal{V}^c}) \ge \tau d - O(\sqrt{d})$. Moreover using Proposition 4.6 and Lemma 7.2, we have $\lambda_1(L(\mathbb{G})|_{\mathcal{V}^c}) = O(N^{-c})$ for any constant $c > 0$ small enough. $\square$

<figure><img src="image_6.png" /></figure>
We now have all the ingredients to prove Proposition 2.5.

*Proof of Proposition 2.5.* We work on $\Xi_1 \cap \Xi_2$ that is a high probability event by Proposition 4.3.

We denote $\mathcal{U} = \cup_{x \in \mathcal{V}} B_2(x) = \cup_{U \in \mathcal{U}} U$ and recall the definition of $\mathcal{U}$ and $\mathbf{q}$ from Definition 4.1 and Proposition 4.6 respectively. We define three vector spaces $E_1 = \text{Span}(\mathbf{q})$, $E_2 = \text{Span}(\{\mathbf{1}_y, y \in \mathcal{U}\})$ and $E_3 = (E_1 + E_2)^\perp$. Let $(v_i, \lambda_i)_{i \le |\mathcal{U}|}$ the eigenvectors-eigenvalues of $L(\mathbb{G})|_{\mathcal{U}}$ that form an orthonormal basis of $E_2$ that decompose into $E_2 = E_2^\perp + E_2^>$ where $E_2^\perp = \text{Span}(\{v_i: \lambda_i \le \frac{1}{2}\tau d\})$ and $E_2^> = \text{Span}(\{v_i: \lambda_i > \frac{1}{2}\tau d\})$. We complete $\{\mathbf{q}, v_1, \dots, v_{|\mathcal{U}|}\}$ into an orthogonal basis for $\mathbb{R}^{[N]} = E_1 + E_2^\perp + E_2^> + E_3$ to obtain an orthogonal matrix $V$. The Laplacian of the graph in this basis is in the form of a block matrix

$$V^*L(\mathbb{G})V = \begin{pmatrix} \nu & 0 & 0 & X_\nu^* \\ 0 & D^{\le q} & 0 & X^\le \\ 0 & 0 & D^> & X^> \\ X_\nu & X^\le & X^> & Y \end{pmatrix}$$

We explain every element of this matrix :

* $\nu = \langle \mathbf{q}, L(\mathbb{G})\mathbf{q} \rangle = O(N^{-c})$ by Proposition 4.6, for $c < \frac{1}{1+t_*}$.

* Because $\text{supp}(\mathbf{q}) \subseteq (\cup_{x \in \mathcal{V}_2} B_3(x))^c$ we have $\text{supp}(L(\mathbb{G})\mathbf{q}) \subseteq (\cup_{x \in \mathcal{V}_2} B_2(x))^c$ and then $L(\mathbb{G})\mathbf{q} \in E_2^\perp$, so we have the two zeros on the first line and column.

* $X_\nu$ is a 1-column matrix that can be identified as a vector such that $L(\mathbb{G})\mathbf{q} = \nu\mathbf{q} + X_\nu$. We have

$$\|X_\nu\| \le \|L(\mathbb{G})\mathbf{q}\| = \|L(\mathbb{G})(\mathbf{q} - \mathbf{e})\| \le \|L(\mathbb{G})\|\|\mathbf{q} - \mathbf{e}\| = O(N^{-c+o(1)})$$

where we use that $L(\mathbb{G})\mathbf{e} = 0$ and Proposition 4.6.

* $D^\le$ and $D^>$ are diagonal matrices with entries $\{\lambda_i: \lambda_i \le \frac{1}{2}\tau d\}$ and $\{\lambda_i: \lambda_i > \frac{1}{2}\tau d\}$. This directly follows from the choice of $v_i$ as the eigenvectors $L(\mathbb{G})|_{\mathcal{U}}$.

* $X^\le$ and $X^>$ describe the adjacency matrix $-A(\mathbb{G})$ between the set $\mathcal{U}$ and $\mathcal{U}^c$ that is a tree by definition of $\Xi_1$ and we have $\max\{\|X^\le\|, \|X^>\|\} \le 2\sqrt{C\bar{d}}$ by Lemma 7.1.

* $Y = L(\mathbb{G})|_{E_3}$. We have $E_1 + E_3 = E_2^\perp = \text{Span}(1_x, x \in \mathcal{U}^c)$. Then if we remove the block matrices associated to the space $E_2$ we obtain

$$V^*L(\mathbb{G})|_{\mathcal{U}^c}V = \begin{pmatrix} \nu & X_\nu^* \\ X_\nu & Y \end{pmatrix} = \begin{pmatrix} \nu & 0 \\ 0 & Y \end{pmatrix} + \begin{pmatrix} 0 & X_\nu^* \\ X_\nu & 0 \end{pmatrix},$$

where we write $V$ instead of $V|_{\mathcal{U}^c}$ and simplify the notation by omitting the zero blocks. We immediately conclude that

$$\lambda_2(L(\mathbb{G})|_{\mathcal{U}^c}) \ge \max\{\nu, \lambda_1(Y)\} - \|X_\nu\|.$$
We have Proposition 4.7 and then use that Span$(1_x, x \in \mathcal{U}^c) \subset \text{Span}(1_x, x \in \mathcal{V}^c)$ so by interlacing we obtain

$$ \frac{1}{2}\tau d \leq \lambda_2(L(\mathbb{G})|_{\mathcal{V}^c}) \leq \lambda_2(L(\mathbb{G})|_{\mathcal{U}^c}). $$

Because of the previous estimate on $\nu$ and $\|X_\nu\|$ we finally conclude that

$$ \lambda_1(Y) \geq \frac{1}{2}\tau d - o(1). $$

* Finally we improve the bound for $\|X^\leq\|$. Let $u_2 \in E_2^\leq, u_3 \in E_3$, we have

$$ |\langle L(\mathbb{G})u_3, u_2 \rangle| = |\langle A(\mathbb{G})u_3, u_2|_{\partial\mathcal{U}} \rangle| \leq 2\sqrt{C}d \|u_3\| \|u_2|_{\partial\mathcal{U}}\| $$

and write $u_2 = \sum_i \alpha_i v_i$ for some $\alpha_i \in \mathbb{R}$. We have

$$ \begin{aligned} \|u_2|_{\partial \mathcal{U}}\|^2 &= \sum_{U \in \mathcal{U}} \|u_2|_{\partial U}\|^2 \\ &= \sum_{U \in \mathcal{U}} \left\| \sum_{\text{Supp}(v_i) \subset U} \alpha_i v_i |_{\partial U} \right\|^2 \\ &\leq \sum_{U \in \mathcal{U}} t_* \sum_{\text{Supp}(v_i) \subset U} \alpha_i^2 \|v_i|_{\partial U}\|^2 \\ &\leq C t_* \sum_{U \in \mathcal{U}} \sum_{\text{Supp}(v_i) \subset U} \alpha_i^2 \frac{\|v_i\|^2}{d^2} \\ &= C t_* \frac{\|u_2\|^2}{d^2} \end{aligned} $$

for some fix $C > 0$ by Proposition 4.5 and therefore

$$ \|X^\leq\| = \sup_{u_2 \in E_2^\leq, u_3 \in E_3} \frac{\langle u_3, L(\mathbb{G})u_2 \rangle}{\|u_3\| \|u_2\|} = O\left(\frac{1}{\sqrt{d}}\right). $$

We now finish the proof of Proposition 2.5 we have

$$ V^* L(\mathbb{G})V = \begin{pmatrix} \nu & 0 & 0 & 0 \\ 0 & D^\leq & 0 & 0 \\ 0 & 0 & D^> & X^> \\ 0 & 0 & X^> & Y \end{pmatrix} + \begin{pmatrix} 0 & 0 & 0 & X_\nu^* \\ 0 & 0 & 0 & X_\nu^\leq \\ 0 & 0 & 0 & 0 \\ X_\nu & X^\leq & 0 & 0 \end{pmatrix} $$

therefore

$$ \sum_{\lambda \in \text{Spec}(L(\mathbb{G}))} \delta_{\lambda} \quad \text{and} \quad \delta_{\nu+\delta_{\nu}} + \sum_{\mu \in \text{Spec}(D^{\leq})} \delta_{\mu+\epsilon_{\mu}} \quad (12) $$

agrees on $[0, \tau d/2 - o(1)]$ with $\delta\nu \leq \|X_\nu\| = O(N^{-c})$ and

$$ \epsilon_{\mu} \leq \min\{\|X^{\leq}\|, \frac{5\|X^{\leq}\|^2}{\frac{1}{2}\tau d - \mu}\} \leq \begin{cases} \frac{1}{\sqrt{d}} & \text{if } \mu \geq \tau d/4, \\ \frac{20}{\tau d^2} & \text{if } \mu \leq \tau d/4 \end{cases} = O((1+\mu)d^{-1}), $$
where we used Lemma 7.2. We now use Proposition 4.4

$$ \sum_{\mu \in \text{Spec}(D \leq)} \delta_{\mu+\epsilon_{\mu}} = \sum_{U \in \mathcal{U}} \sum_{\mu \in \text{Spec}(L(\mathbb{G})|_U)} \delta_{\mu+\epsilon_{\mu}} = \sum_{F \in \mathfrak{F}} \sum_{\mu \in \text{Spec}(L(F; \partial F))} \delta_{\mu+\epsilon_{\mu}+\epsilon'_{\mu}} \quad (13) $$

with $\epsilon'_{\mu} = O((\mu + 1)d^{-1})$. Combining (12) and (13) gives the right-hand side term of Proposition 2.5. Finally because the multiplicity of the eigenvalue $\{0\}$ of $L(\mathbb{G})$ is equal to the number of connected component in the graph, we actually have that $\delta_{\nu+\delta\nu} = \delta_0$ (which can be seen as the eigenvalue associated with the giant connected component). $\square$

# 5 Spectrum of weighted Laplacian on trees, Proof of Proposition 2.6.

In this section, we prove that the line is the optimal graph to minimize the smallest non-zero eigenvalue and then compute explicitly its spectrum.

**Proposition 5.1.** For any tree $T$ of size $|T| \leq t$ and $\hat{X} \subset [[T]]$ we have

$$ \lambda_1(L(\mathbb{L}_t, \{1\})) \leq \min(\text{Spec}(L(T, \hat{X}))) \setminus \{0\}. \quad (14) $$

Note that since the number of trees of size $t$ is finite and since increasing the size of a multiset is a positive rank-one perturbation of the corresponding deformed Laplacian matrix, Proposition 5.1 tells that for any $t \in \mathbb{N}$ there exists a universal constant $c>0$ such that $\lambda_1(L(\mathbb{L}_t, \{1\})) \leq \min(\text{Spec}(L(T, \hat{X}))) \setminus \{0\}$-c, for every tree $T$ of size $t$ and any multiset on $[[T]]$.

**Lemma 5.2.** The eigenvalues $L(\mathbb{L}_t, \{1\})$ are $\lambda_k = 2 - 2 \cos(\frac{\pi}{2t+1} + \frac{2k\pi}{2t+1})$ for $0 \leq k < t$.

*Proof of Proposition 2.6.* This directly follows from Proposition 5.1 and Lemma 5.2 with $t = t_*$.

*Proof of Proposition 5.1.* We are interesting in the minimiser of $\min(\text{Spec}(L(T, \hat{X}))) \setminus \{0\}$ among all the tree $T$ of size $|T| \leq t$. For any $i \in T$, $1_i 1_i^*$ is positive operator therefore we have that for all multiset $\hat{X} \subset \hat{Y} \subset [[T]]$, $L(T, \hat{X}) \leq L(T, \hat{Y})$ (as operator) and then

$$ \lambda_1(L(T, \hat{X})) \leq \lambda_1(L(T, \hat{Y})) $$

In the case $\hat{X} = \emptyset$ we have $\lambda_1(L(T, \emptyset)) = \lambda_1(L(T)) = 0$ and by interlacing we have

$$ 0 = \lambda_1(L(T, \emptyset)) < \lambda_1(L(T, \{i\})) < \lambda_2(L(T, \emptyset)). $$

If $|T| < t$ there exists a large graph $T'$ with $|T'| = t$ such that $T \subset T'$ and again by interlacing we have

$$ 0 < \lambda_1(L(T', \{i\})) < \lambda_1(L(T, \{i\})) $$
Therefore the minimiser is of the form $\lambda_1(L(T, \{i\}))$ with $|T| = t$.

We think of $i$ as the root of $T$ and for every edge $e = (x, y)$ of $T$ we define the weight

$$q(e) = u(x) - u(y)$$

and denote $\mathbf{q} = (q_e)_{e \in E} \in \mathbb{R}^{t-1}$. We have

$$\lambda_1(L(T, \{i\})) = \inf_{u \in \mathbb{R}^t \setminus \{0\}} \frac{\langle u, L(T, \{i\})u \rangle}{\|u\|^2} = \inf_{u \in \mathbb{R}^t \setminus \{0\}} \frac{\sum_{e \in E} q(e)^2 + |u(i)|^2}{\|u\|^2}. \quad (15)$$

Let us now change to a dual approach. We have a bijection between $\{u(i), \mathbf{q}\}$ and $(u(x))_{x \in T}$ given by the equation

$$u(x) = u(i) + \sum_{e \in P_{i \to x}(T)} q(e) \quad (16)$$

where we denoted by $P_{i \to x}(T)$ the unique path from $i$ to $x$ in $T$. We denote $u = \phi(T, i, u(i), \mathbf{q})$ the bijection of Equation (16). Then we have

$$\min_{T,i} \lambda_1(L(T, \{i\})) = \inf_{u(i), \mathbf{q}} \min_{T,i} \frac{\sum_e |q(e)|^2 + |u(i)|^2}{\|\phi(T, i, u(i), \mathbf{q})\|^2} = \inf_{u(i), \mathbf{q}} \max_{T,i} \frac{\sum_e |q(e)|^2 + |u(i)|^2}{\|\phi(T, i, u(i), \mathbf{q})\|^2}.$$

We now show that for fixed $u(i), \mathbf{q}$ the norm $\|\phi(T, i, u(i), \mathbf{q})\|^2$ is maximized when $T$ is the line and $i$ an extremal point.

We sort the edges decreasingly according to their weight

$$|q(e_1)| \ge |q(e_2)| \ge \dots \ge |q(e_{t-1})| \ge 0$$

and the vertices increasingly according to their graph distance to the root $i = x_0$

$$0 \le \mathrm{dist}(i, x_1) \le \mathrm{dist}(i, x_2) \le \dots \le \mathrm{dist}(i, x_{t-1}).$$

We have

$$\left| \sum_{e \in P_{i \to x_k}} q(e) \right| \le \sum_{e \in P_{i \to x_k}} |q(e)| \le \sum_{l=1}^{|P(i, x_k)|} |q(e_i)| \le \sum_{l=1}^k |q(e_i)|,$$

where we use that the length of the path $P(i, x_k)$ is at most $k$. Therefore

$$\|\phi(T, i, u(i), \mathbf{q})\|^2 = \sum_{k=0}^{t-1} |u(i)| + \sum_{e \in P_{i \to x_k}} q(e)^2 \le \sum_{k=0}^{t-1} \left| |u(i)| + \sum_{l=1}^k |q(e_i)| \right|^2 \quad (17)$$

Observe that the right-hand side can be reached if $T$ is a line and $i$ is an extremal point. Moreover this solution is unique if $q(e_i) > 0$ for all $i \le t-1$. Then we have

$$\max_{T,i} \|\phi(T, i, u(i), \mathbf{q}, T)\|^2 = \|\phi(\mathbb{L}_t, 1, u(i), \mathbf{q})\|^2$$
and finally conclude that $\min_{T,i} \lambda_1(L(T, \{i\})) = \lambda_1(L(\mathbb{L}_t, \{1\}))$.

Finally, we now prove that we can assume $|q(e_{t-1})| > 0$. If $q(e_{t-1}) = 0$ then

$$ \frac{d}{dq(e_{t-1})} \left( \sum_e |q(e)|^2 + |u(i)|^2 \right) = 0, \quad \frac{d}{dq(e_{t-1})} \sum_{k=0}^{t-1} \left| u(i) + \sum_{l=1}^{k} |q(e_l)| \right|^2 \neq 0, $$

therefore $q$ is not the minimser of

$$ \inf_{u(i), q} \frac{\sum_e |q(e)|^2 + |u(i)|^2}{\|\phi(\mathbb{L}_t, 1, u(i), q)\|^2}. $$

□

*Proof of Lemma 5.2.* We write the matrix

$$ L(\mathbb{L}_t, \{1\}) = \begin{pmatrix} 2 & -1 & 0 & \cdots & 0 & 0 \\ -1 & 2 & -1 & 0 & 0 & 0 \\ 0 & -1 & \cdots & \cdots & \vdots & 0 \\ \vdots & 0 & \cdots & \cdots & \cdots & 0 \\ 0 & 0 & \cdots & 0 & 2 & -1 \\ 0 & 0 & \cdots & 0 & -1 & 1 \end{pmatrix} \in \mathbb{R}^{t \times t}. $$

Let $\lambda$ an eigenvalue and and $u \in \mathbb{R}^{t+1}$ the associated eigenvector with the convention $u_0 = 0$. We have

$$ Lu = \lambda u \iff \begin{cases} u_{k+1} + u_{k-1} = (2-\lambda)u_k & \text{for } 1 \le k < t \\ u_{t-1} = (1-\lambda)u_t & \end{cases} $$

Therefore for any $1 \le k < t$

$$ \begin{pmatrix} u_{k+1} \\ u_k \end{pmatrix} = P \begin{pmatrix} u_k \\ u_{k-1} \end{pmatrix} = P^k \begin{pmatrix} u_1 \\ 0 \end{pmatrix} \quad \text{with} \quad P = \begin{pmatrix} (2-\lambda) & -1 \\ 1 & 0 \end{pmatrix}. $$

Let $\alpha \in [0, \frac{\pi}{2}]$ such that $2 - \lambda = 2 \cos \alpha$ then the eigenvalues of $P$ are solution of $\gamma^2 - 2 \cos(\alpha)\gamma + 1 = 0$ which are

$$ \gamma_{\pm} = \frac{2 \cos(\alpha) \pm i \sqrt{4 - 4 \cos(\alpha)^2}}{2} = \cos \alpha \pm i \sin \alpha = e^{\pm i \alpha}. $$

Then $u_k = ae^{ik\alpha} + be^{-ik\alpha}$ for some $a, b \in \mathbb{C}$ and with $u_0 = 0$ we conclude that $u_k = \sin(k\alpha)$ up to a multiplicative factor. Finally, the last equation becomes

$$ (2 \cos \alpha - 1) \sin(t\alpha) = \sin((t-1)\alpha) $$

and using the recursive algorithm for finding the nth multiple angle, we see that

$$ \sin((t+1)\alpha) = 2 \cos(\alpha) \sin(t\alpha) - \sin((t-1)\alpha) = \sin(t\alpha). $$

We conclude that $\sin((t+1)\alpha) = \sin(t\alpha)$ and thus

$$ \alpha = \frac{\pi}{2t+1} \mod \left( \frac{2\pi}{2t+1} \right). $$

□
# 6 Outlook

## 6.1 Fluctuations and eigenvector localization

With Theorem 1.1 we understand the distribution of the smallest eigenvalues of $L$ but at a deterministic level. A natural development would be to improve such a prediction to obtain the fluctuation scale and its asymptotic law. Also Theorem 1.1 does not give any information about the corresponding eigenvectors but the proof hints at the fact that there exists a narrow relation between the smallest eigenvalues of $L$ and some specific geometric objects that can be found in $G$, namely trees of a particular shape. We believe that this relation can be made into a rigorous mathematical result by showing that the eigenvectors corresponding to the smallest eigenvalues are localized on the lines of maximal size. The work to get there is non-trivial but a very similar result has been done in previous work ([ADK21b, Theorem 1.7] as well as in [Riv23]. Inspired by these works we expect the following to hold:

**Conjecture 6.1.** There is an interval $[a, b]$, with $a, b$ close to $2 - 2 \cos(\frac{\pi}{2t_*+1})$ such that

1. $\lambda_2 \in [a, b]$ with high probability.

2. (Fluctuations) $\sum_{\lambda \in \text{Spec}(L(\mathbb{G}))} \delta_{\lambda}$ converge to a Poisson Point Process on $[a, b]$.

3. (Localization) For any $\lambda \in [a, b]$ and $v$ the corresponding eigenvector, there exists a tree $T \subset \mathbb{G}$ that is isomorphic to line of size $t_*$ and such that $\|v|_T\| = 1 - o(1)$

Following the strategy in [ADK21c] one have to improve the bijection of Proposition 2.5 such that the error terms $\epsilon_\mu$ are much smaller. We believe that this could be done analyzing the Laplacian on a neighborhood $U$ of $F \subset U$ instead of $L(F; \partial \tilde{F})$. For the first orders one should replace the computation of the spectrum of $L(\mathbb{L}_t, \{1\})$ by the one of the following tridiagonal matrix

$$ M := M(t_*, D_z, |S_2(z)|) = \begin{pmatrix} 1 & -1 & 0 & \cdots & 0 & 0 \\ -1 & 2 & -1 & 0 & & 0 \\ 0 & -1 & \ddots & \ddots & & \vdots \\ \vdots & 0 & \ddots & \ddots & & \vdots \\ & & & & 2 & -1 & 0 \\ & & & -1 & D_z & \sqrt{D_z} \\ 0 & & & & & \frac{|S_2(z)|}{D_z} \\ 0 & 0 & \cdots & & 0 & \sqrt{D_z} \end{pmatrix} \in \mathbb{R}^{t_*+2 \times t_*+2}. \quad (18) $$

We claim that there exists an eigenvalue of $L(\mathbb{G})$ such that $\lambda = \lambda_1(M) + O(d^{-2})$ and that we can obtain

$$ \lambda_1(M) = 2 - 2 \cos\left(\frac{\pi}{2t_*+1}\right) + \delta(D_z, |S_2(z)|) + O(d^{-2}), \quad (19) $$
for some explicit function $\delta: \mathbb{R}^2 \to \mathbb{R}$.

<figure><img src="image_7.png" /><figcaption>Figure 2: Illustration of the intermediate regime. We expect lines of size $t_* + 1$ to appear as a result of the erosion of the anchor of lines of size $t_*$.</figcaption></figure>

We should also improve Proposition 2.4 having not only the existence of the line but controlling the degree of the anchor as well: $\{T \sim L_t, z \text{ anchor with } D_z = \alpha d\}$ for some $\tau \le \alpha < 1$. Because of (19), the smallest eigenvalue would be obtained with the smallest possible degree of the anchor. We expect it to be close to $cd$ where

$$N^{1-t^*d+o(1)} \times \mathbb{P}(D_z = cd) \asymp 1. \qquad (20)$$

We then would choose the interval $[a, b]$ as a small neighborhood of $2-2\cos(\frac{\pi}{2t_*+1})+\delta(cd, cd^2)$. Finally, the main ingredient for the localization is an estimate on $|\lambda_i - \lambda_j| \gg \max\{\epsilon_i, \epsilon_j\}$ combined with Lemma 7.2. An upper bound on $\max\{\epsilon_i, \epsilon_j\}$ should come from the improve rigidity result above while a lower bound on $|\lambda_i - \lambda_j|$ should be a consequence of the Poisson point process statistic and its limiting law.

## 6.2 Intermediate regime

We now add a few remarks about the intermediate regime

$$(1 - \epsilon) \frac{\log N}{t_*} \le d \le (1 + \epsilon) \frac{\log N}{t_*}.$$

In our paper the condition (1) is needed for two properties : the existence of a line of size $t_*$ and to make sure that all the vertices in its neighborhood have large degree (for a spectral gap and to do perturbations theory). In the intermediate regime, the existence of component of size $t_*$ becomes random but we still have with high probability a line of size $t_* - 1$ and no connected component of size $t_* + 1$. Therefore one could expected that $\lambda_2$ is random but because of Propositions 2.4, 2.5, 2.6 we can still state the following.

**Proposition 6.2.** In the intermediate regime with high probability

$$2 - 2 \cos \left( \frac{\pi}{2t_* + 1} \right) + O(d^{-1}) \le \lambda_2 \le 2 - 2 \cos \left( \frac{\pi}{2t_* - 1} \right) + O(d^{-1})$$
To refine the analysis, we expect the degree of the anchor $D_z$ to play a major role in the transition from the $t_*$ line regime to the $t_*+1$ line regime, going from $D_z \ge \tau d$ for $d \approx (1+\epsilon)^{\frac{\log N}{t_*+1}}$ and decreasing to $D_z \sim 1$ for $d \approx \frac{\log N}{t_*+1}$ therefore creating a $t_*+1$ line. One could then try to use (19) to compute $\lambda_2$ in the intermediate regime. However, because the predictions obtained from the spectrum of finite trees only give discrete values, there should exist regimes of $d$ for which $\lambda_2$ is random with fluctuations $\asymp 1$. An illustration of our heuristics is given in Figure 2.

## 6.3 Numerical simulations

<figure><img src="image_8.png" /><figcaption>Figure 3: We plotted the spectral gap of $L$ for various regimes of $d$ below the criticality threshold. Simulations were obtained with $N = 10^4$, $d = \frac{1}{t} \log N$ for values of $1 \le t \le 3.2$.</figcaption></figure>

In this section, we compare our estimates from Theorem 1.1 with numerical simulations presented in Figure 3 and 4. Using Theorem 1.1, we obtain a first-order approximation (dark red): note that this estimate only depends on $\lfloor t \rfloor$ (see (2)) and is thus a piece-wise constant function. The error between the dark red line and the blue dots remains of the order $O(d^{-1})$, in agreement with (2) (indeed for $N = 10^4$, $1/d \sim 0.1$). We expect the fit to become much better
<figure><img src="image_9.png" /><figcaption>Figure 4: We plotted the spectral gap of $L$ for $d \ge \frac{1}{2} \log N$. Simulations were obtained with $N = 10^4$, $d = \frac{1}{t} \log N$ for values of $0.6 \le t \le 1$.</figcaption></figure>

as $d \to +\infty$, but unfortunately, since $d \asymp \log N$, we would need to simulate exponentially large graphs to reduce the error, which is infeasible in practice. Second, we can use the discussion at the beginning of the second to approximate $\lambda_2(L)$ by $\lambda_1(M)$ for $M$ defined in (18). The matrix $M$ has three parameters namely $t_*$ which corresponds to $|t|$, $D_z$ and $|S_2(z)|$. We set $D_z = cd$, $c > 0$, to be the (expected) smallest degree of any anchor of a line of size $t_*$ and $|S_2(z)| = dD_z$ (see the discussion leading to (20)). The second-order approximation seems to fit the numerical results much more closely, than the first-order approximation. The simulations are displayed in Figure 3.

To give a more complete view of the behavior of the spectral gap, we also provide simulations for $d \ge \log N$ on Figure 4. It was shown in [Riv23][Chapter 3] that the spectral gap of $L$ in these regimes was given to the first order by $\Delta + \frac{d}{\Delta-d}$, $\Delta := \min_{x \in [N]} D_x$. Therefore, whenever $d \ge \log N$, we use $\Delta$ as a first order approximation for $\lambda_2(L)$ (dark green line) and $\Delta + \frac{d}{\Delta-d}$ as a second order approximation (light green line). In the subcritical regime, we can approximate $\lambda_2(L)$ in two different ways.
# 7 Appendix

We mention [ADK21c, Lemma E.1 and E.5].

**Lemma 7.1.** For $T$ a tree with degrees bounded by $M > 0$ and $A$ its adjacency matrix we have $\|A\| \le \sqrt{2M}$.

**Lemma 7.2.** Let $M$ be a self-adjoint matrix. Let $\epsilon, \Delta > 0$ satisfy $5\epsilon \le \Delta$. Let $\lambda \in \mathbb{R}$ and suppose that $M$ has a unique eigenvalue $\mu$ in $[\lambda - \Delta, \lambda + \Delta]$, with corresponding normalized eigenvector $w$. If there exists a normalized vector $v$ such that $\|(M - \lambda)v\| \le \epsilon$ then

$$ \mu - \lambda = \langle v, (M - \lambda)v \rangle + O\left(\frac{\epsilon^2}{\Delta}\right), \quad \|w - v\| = O\left(\frac{\epsilon^2}{\Delta}\right). $$

# References

[ADK21a] Johannes Alt, Raphael Ducatez, and Antti Knowles. Delocalization transition for critical Erdős-Rényi graphs. *Communications in Mathematical Physics*, 388(1):507–579, 2021.

[ADK21b] Johannes Alt, Raphaël Ducatez, and Antti Knowles. Extremal eigenvalues of critical Erdős-Rényi graphs. *The Annals of Probability*, 49(3):1347–1401, 2021.

[ADK21c] Johannes Alt, Raphael Ducatez, and Antti Knowles. Poisson statistics and localization at the spectral edge of sparse Erdős-Rényi graphs. *arXiv preprint arXiv:2106.12519*, 2021.

[BB98] Béla Bollobás and Béla Bollobás. *Random graphs*. Springer, 1998.

[CLO+22] Andrew Campbell, Kyle Luh, Sean O'Rourke, Santiago Arenas-Velilla, and Victor Pérez-Abreu. Extreme eigenvalues of laplacian random matrices with gaussian entries. *arXiv preprint arXiv:2211.17175*, 2022.

[ER60] Paul Erdős and Alfréd Rényi. On the evolution of random graphs. *Publ. Math. Inst. Hungar. Acad. Sci*, 5:17–61, 1960.

[HL20] Jiaoyang Huang and Benjamin Landon. Spectral statistics of sparse Erdős-Rényi graph laplacians. In *Annales de l'Institut Henri Poincaré, Probabilités et Statistiques*, volume 56, pages 120–154. Institut Henri Poincaré, 2020.

[JRL11] Svante Janson, Andrzej Rucinski, and Tomasz Luczak. *Random graphs*. John Wiley & Sons, 2011.

[Riv23] Renaud Rivier. *The Laplacian of the Erdős-Rényi graph*. PhD thesis, University of Geneva, 2023.