Bernoulli flow for Erd s-R'enyi graphs
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: I'm Ada.
Emmy: And I'm Emmy, here with Kolya.
Ada: We're looking at the paper: "Bernoulli flow for Erd s-R'enyi graphs".
Emmy: Here's the gist of the paper. We study the eigenvalues and eigenvectors of the adjacency matrix A of an Erdős-Rényi graph G(N, p) in the regime where N p much greater than (N) squared.
Ada: The primary objectives are to establish optimal isotropic delocalization for the bulk eigenvectors u, meaning that v, u squared at most C N / N with very high probability for any deterministic normalized vector v.
Emmy: Furthermore, we prove local spectral universality in the bulk by demonstrating that the local spectral statistics coincide with those of the Gaussian Orthogonal Ensemble (GOE).
Ada: The core methodological innovation is the introduction of a new approach to local laws termed the Bernoulli flow.
Paper summary: Ada: So we’re looking at this paper called Bernoulli flow for Erdős-Rényi graphs. It focuses on finding eigenvalues and eigenvectors of that adjacency matrix A for a graph G with N nodes and p edges, specifically when the number of edges is much larger than the square of the logarithm of N, so N p is much bigger than log to the power of two n.
Emmy: Right, it’s about figuring out how these eigenvectors behave in that regime. The main claims are establishing optimal isotropic delocalization for those bulk eigenvectors and proving local spectral universality in the bulk by showing it matches the Gaussian Orthogonal Ensemble or GOE statistics.
Kolya: I'm interested in what that delocalization actually means for someone. It says the squared inner product between any deterministic normalized vector and these bulk eigenvectors is bounded by C times log N over N with very high probability, and they show this holds down to the threshold of n p being much bigger than log to the power of two n (<ref:2609.15566#pg1>).
Ada: Exactly. It’s saying that for these bulk eigenvectors, they are spread out optimally for any fixed deterministic vector you pick, and this holds even when N p is barely above that threshold. That's a strong statement about the eigenvector structure in sparse random graphs.
Emmy: And beyond that delocalization, they prove local spectral universality in the bulk because the statistics of nearby eigenvalues look like those of the GOE, which means they follow a Sine one point process when you zoom in on small eigenvalue spacings (<ref:2609.15566#pg3>).
Kolya: I wonder what that universality implies for practical applications? If the local statistics match the GOE, does that mean we can use those same tools to predict behavior in other complex systems where randomness plays a role? What kind of tail is this distribution governing, and do those constants stay stable when we apply it to something bigger than these graphs (<ref:2609.15566#pg3>)?
Ada: That’s a good question about stability. They tackle the underlying structure using a new approach they call the Bernoulli flow, which replaces the usual Brownian process with one where each edge is an independent Markov process jumping from closed to open at a unit rate (<ref:2609.15566#pg1>).
Emmy: That replacement is key because it lets them target the desired distribution directly without needing those intermediate comparison steps that other dynamical methods require, which is a big deal in sparse random matrix theory. They have two components to this flow: the Bernoulli process itself and a deterministic matrix-valued characteristic flow for the spectral parameter (<ref:2609.15566#pg1>).
Paper summary: Kolya: So the Bernoulli process is essentially modeling how connectivity evolves on an edge level, and that’s what dictates the spectral behavior? If we look at the results, they establish this local law for the resolvent of A down to optimal spectral scales with optimal error bounds (<ref:2609.15566#pg3>).
Ada: That local law is what makes everything else follow. It means that because of this flow, they can prove those two major results: the optimal delocalization and the bulk universality. They use four martingales associated with average and entrywise observables to show these observables are much smaller than the threshold level of a stopping time, which basically proves that this stopping time is at the optimal scale (<ref:2609.15566#pg3>).
Emmy: It’s interesting how they connect the local law for the resolvent with a very recent result by Bourgade and Huang, which uniquely characterizes the Sine one point process via loop equations on the spectral scale of mean eigenvalue spacing (<ref:2609.15566#pg3>). That connection is what verifies bulk universality down to n p being much bigger than log to the power of two n plus kappa.
Kolya: So, if we think about what this means for a listener who doesn't study random matrices, it’s that when you have a very large sparse network, the eigenvectors are highly spread out in a predictable way, and the spacing between their eigenvalues follows a specific pattern dictated by the GOE statistics.
Ada: And they show this behavior persists even when you push the edge density slightly beyond that threshold of n p being much bigger than log to the power of two n plus kappa. That's about how robust this structure is.
Emmy: But we have to remember what they didn't do, which is the local laws for fixed spectral parameters themselves, though they tackle that with Theorem two point two (<ref:2609.15566#pg3>). They prove those local laws by showing the quadratic variation of martingales and bounding jump sizes using resolvent expansions and stochastic Grönwall estimates (<ref:2609.15566#pg3>).
Kolya: That sounds like a lot of technical machinery to control everything at once, especially getting those error bounds tight enough for fixed spectral parameters. What is the practical limit here? Where does this Bernoulli flow stop working reliably?
Ada: The paper states that they proved the optimal isotropic delocalization down to the threshold of n p much bigger than log to the power of two n (<ref:2609.15566#pg1>). They also confirm bulk universality down to n p much bigger than log to the power of two n plus kappa (<ref:2609.15566#pg3>).
Paper summary: Emmy: The main limitation mentioned is that they still need to prove those local laws for fixed spectral parameters, which involves controlling generator terms using resolvent expansions and martingale concentration inequalities (<ref:2609.15566#pg3>). That control over the jump sizes and the generator terms is where the proof gets very intricate.
Kolya: So what does this mean for someone who just wants to know if a system is delocalized or localized? This paper gives them a precise mathematical statement about how spread out those eigenvectors are in dense graphs, suggesting a level of structure that goes beyond simple random expectation (<ref:2609.15566#pg2>).
Ada: It suggests that for these large sparse systems, the delocalization isn't just random; it's optimally spread out with respect to any deterministic vector you choose, which is a very precise statement about the structure of the eigenvectors (<ref:2609.15566#pg1>).
Emmy: The Bernoulli flow approach itself is significant because it avoids comparison steps, meaning they are directly targeting the required distribution via a matrix-valued characteristic flow (<ref:2609.15566#pg1>). It’s a cleaner way to establish these local laws than older dynamical methods that rely on comparing processes (<ref:2609.15566#pg3>).
Kolya: From a probabilistic viewpoint, the fact that they use concentration inequalities for sums of Bernoulli random variables is important because it tells us how likely we are to see those extreme deviations from the expected behavior (<ref:2609.15566#pg3>). It governs the tail behavior of these error terms.
Ada: The overall implication is that we have a very strong local law for the resolvent of A down to optimal spectral scales with optimal error bounds, which is the engine driving both results (<ref:2609.15566#pg3>). This control allows them to confirm the bulk universality by verifying microscopic loop equations at a scale where Im z is approximately one over N (<ref:2609.15566#pg3>).
Emmy: So, to wrap up this paper, Bernoulli flow for Erdős-Rényi graphs shows that in the sparse regime of very large random graphs, we can precisely characterize how delocalized the eigenvectors are and confirm that their local eigenvalue statistics follow the GOE distribution (<ref:2609.15566#pg3>).
Kolya: It suggests a deep structural coherence in these systems, where even in high randomness, there's an underlying order governed by this specific flow dynamics.
Ada: Exactly. The paper proves that this behavior holds down to the threshold of n p being much bigger than log to the power of two n plus kappa (<ref:2609.15566#pg3>).
Emmy: We’ll wrap up here, but keep an eye on how these flow techniques apply to other types of random matrices or sparse systems where we need strong control over local spectral behavior.
Conclusion: Ada: So we've been looking at this paper called "Bernoulli flow for Erdős-Rényi graphs." Basically, they're showing how to precisely measure something in these massive random networks by using a new way of tracking how connections change over time.
Emmy: Right, it’s about taking the usual tools we use for analyzing random matrices and replacing them with this Bernoulli flow. It’s a Markov process on the edges that jumps when they open up, which lets them target the exact spectral statistics they want without needing those messy comparison steps.
Kolya: And what they found is that this method gives them a really sharp control over how spread out the main eigenvectors are in these large graphs. They prove this holds down to a specific edge density where n p is much bigger than log to the power of two n.
Ada: So, the core idea is that even in these very sparse, large random graphs, you can predict exactly how delocalized any eigenvector will be for any deterministic vector you pick. It’s not just some vague expectation; it’s a precise bound on how much it spreads out.
Emmy: And they also showed that the local structure of the eigenvalues in the middle—the bulk—actually matches what we see in something called the Gaussian Orthogonal Ensemble, or GOE statistics. That's a strong link to other mathematical physics models.
Kolya: For someone listening, that means if you zoom into the middle part of a huge random graph, its eigenvalue spacing follows a very specific pattern governed by this GOE rule. It suggests there’s a deep structural order underneath the randomness that we can actually measure.
Ada: It really does suggest that these large sparse systems have more structure than we usually think they do when you just look at the raw randomness of the edges. They've set a very clear benchmark for what this behavior looks like in these graphs.
Emmy: This work lays a foundation for using dynamical flows, like this Bernoulli flow, to study spectral properties in much more complex systems beyond just Erdős-Rényi graphs.
Kolya: And there’s still that part they have to tackle—getting the local laws for fixed spectral parameters right. That involves really careful math with martingales and error bounds, which is where the technical meat of their proof lies.
Ada: We'll keep digging into those details later, but for now, this paper establishes a very solid framework for understanding eigenvector behavior in these large random networks and linking them to known statistical models.
math.PR, math-ph, math.MP
Submitted: 2026-09-14
Updated: 2026-11-10
Comments: Minor corrections and updated references
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 92/100
The gist: We study the eigenvalues and eigenvectors of the adjacency matrix A of an Erdős-Rényi graph G(N, p) in the regime where N p much greater than (N) squared.
Key concepts
- Optimal Delocalization
- This means that for any deterministic vector $\mathbf{v}$, its correlation with an eigenvector $\mathbf{u}$ is very small, bounded by $C \log N / N$. This proves the bulk eigenvectors are well-spread and not concentrated in a few places, which is crucial for spectral analysis.
- Bernoulli Flow
- This is a new technique replacing standard Brownian motion. It models edge dynamics as independent Markov processes where edges jump from closed to open at unit rate. The spectral parameter flows according to this process, directly targeting the desired eigenvalue distribution without needing intermediate comparison steps.
- Bulk Universality
- This concept states that the local statistics of eigenvalues in a large random graph behave like those of a known mathematical model, specifically the Gaussian Orthogonal Ensemble (GOE). This is confirmed by showing that the rescaled microscopic eigenvalue process converges to a Sine1 point process.
- Sine1 Point Process
- This is the specific statistical distribution that describes the local behavior of eigenvalues in this context. Its convergence confirms bulk universality, meaning that as $N$ grows, the local spectral statistics of random graphs follow this well-understood pattern.
Terminology
Summary
We study the eigenvalues and eigenvectors of the adjacency matrix A of an Erdős-Rényi graph G(N, p) in the regime where N p much greater than (N) squared. p. 0 Bernoulli flow for Erdős-Rényi graphs
Joscha Henheik Antti Knowles
September 15, 2026
We study the eigenvalues and eigenvectors of the adjacency matrix A of the Erdős-Rényi graph
G(N, p) in the regime N p ≫ (log N)
2
. We establish optimal isotropic delocalization for the bulk
eigenvectors u, meaning that ⟨v ,u⟩
2 ⩽
C log N
N with very high probability for any deterministic
normalized v. Bernoulli flow for Erdős-Rényi graphs
Joscha Henheik Antti Knowles
September 15, 2026
We study the eigenvalues and eigenvectors of the adjacency matrix A of the Erdős-Rényi graph
G(N, p) in the regime N p ≫ (log N)
2
. We establish optimal isotropic delocalization for the bulk
eigenvectors u, meaning that ⟨v ,u⟩
2 ⩽
C log N
N with very high probability for any deterministic
normalized v. We establish optimal isotropic delocalization for the bulk
eigenvectors u, meaning that ⟨v ,u⟩
2 ⩽
C log N
N with very high probability for any deterministic
normalized v. In addition, we prove local spectral universality in the bulk by showing that the
local spectral statistics coincide with those of the GOE.Where the paper says it
Where the paper says it
Where the paper says it
The core methodological innovation is the introduction of a new approach to local laws termed the Bernoulli flow. p. 0 The main tool of our proof is a local
law for the resolvent of A, down to optimal spectral scales and with optimal error bounds. Its
proof relies on a new approach to local laws that we call the Bernoulli flow. Its
proof relies on a new approach to local laws that we call the Bernoulli flow. It is a characteristic
flow method in which the usual Brownian process is replaced by a Bernoulli process, where each
edge of the graph forms an independent Markov process that jumps at unit rate from closed to
open. It is a characteristic
flow method in which the usual Brownian process is replaced by a Bernoulli process, where each
edge of the graph forms an independent Markov process that jumps at unit rate from closed to
open. The spectral parameter flows according to a suitably constructed matrix-valued Bernoulli
characteristic flow. The key advantage of replacing the Brownian flow with the Bernoulli flow is that the flow does not
generate a Gaussian component, instead flowing directly to the desired target distribution. Hence,
no comparison step is required, thus avoiding the key hurdle in establishing local laws for sparse
random matrices using dynamical methods. (i) The Bernoulli process (X(t))0⩽t⩽T , a Markov jump process on the space of adjacency matrices. (ii) The Bernoulli characteristic flow (zt)0⩽t⩽T , a deterministic matrix-valued flow for the spectral
parameter.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The main results are:
-
Optimal Delocalization: Theorem 1.1 states that under certain conditions on N p, for any deterministic v in R N and any normalized eigenvector u of H with eigenvalue lambda satisfying lambda at most 2 - kappa, we have v, u squared at most C (N / N) v e with probability at least 1 - N-D. p. 3
This optimal delocalization is shown to be achieved down to the threshold N p much greater than (N) squared. p. 3Where the paper says it
Then, for any deterministic v ∈ R N and any normalized eigenvector u of H with eigenvalue λ satisfying |λ| ⩽ 2 − κ, we have ⟨v,u⟩ 2 ⩽ C log N N ∥v∥ 2 e (1. 5) with probability at least 1 − N −D.
Where the paper says it
5 below for more details. In fact, although delocalization is known to hold down to N p ≫ log N, it is not clear that optimal delocalization must hold down to the same threshold.
-
Bulk Universality: Theorem 1.2 establishes bulk universality, meaning GOE local spectral statistics for H. p. 0
It states that under certain conditions on N p, as N to infinity, the rescaled microscopic eigenvalue process of H around E converges in distribution to the Sine1 point process. p. 4Where the paper says it
We establish optimal isotropic delocalization for the bulk eigenvectors u, meaning that ⟨v ,u⟩ 2 ⩽ C log N N with very high probability for any deterministic normalized v. In addition, we prove local spectral universality in the bulk by showing that the local spectral statistics coincide with those of the GOE.
This universality is confirmed down to the threshold N p much greater than (N) squared + kappa. p. 6Where the paper says it
Explicitly, Theorem 1. 2 states that for any continuous and compactly supported function f, the random variable R f dµ E converges in distribution to a corresponding random variable where the point process µ E is replaced with the Sine1 process.
Where the paper says it
In [7,9], the optimal region of delocalization in terms of the energy and the critical density N p log N was determined. Bulk universality for Wigner matrices was established in the landmark series of papers [55–65] as well as in [98,99], and later gradually extended to dense mean field ensembles of greater generality: for Wigner matrices with diagonal [88] and non-diagonal deformations [72, 82], Wigner-type ensembles with not necessarily identically distributed but still independent entries [5], and random matrices with weakly correlated entries [6, 47].
The proof strategy for these results involves establishing a local law for the resolvent of A down to optimal spectral scales and with optimal error bounds, utilizing four martingales associated with average and entrywise observables. p. 0 In addition, we prove local spectral universality in the bulk by showing that the
local spectral statistics coincide with those of the GOE. The main tool of our proof is a local
law for the resolvent of A, down to optimal spectral scales and with optimal error bounds. 3 24
5 Resolvent expansions: Proofs of Lemmas 4. 3 26
6 General isotropic local law 42
7 Local spectral statistics: Proof of Theorem 1.Where the paper says it
Where the paper says it
The proof of Theorem 2. p. 0 The spectral parameter flows according to a suitably constructed matrix-valued Bernoulli
characteristic flow. Contents
1 Introduction 2
2 Local law and proof of Theorem 1. Another important new component of our proof is an analysis of the jump sizes of various observables
under the Bernoulli process, required to control the quadratic variation of the Dynkin martingale. To prove local spectral universality, our verification of the loop equations from [25] uses a standard
cumulant expansion that is controlled using our local law. N p ≪ 1, the bulk universality result from Theorem 1. 2 is new only in the very sparse regime
(log N)
2+κ ⩽ N p ⩽ No(1), since the case N p ⩾ No(1) was previously treated in [77]. Essentially, the latter arises
from the third-order remainder term of a cumulant expansion used to verify the GOE loop equations,
which balances a term θ ≍ √
1
Np
with a resolvent entry Gab. Since the whole argument takes place
at the microscopic spectral scale η ≍
1
N
and our local law controls the entries of G with very high
probability by O(1) at the optimal scale η ≍
log N
N
, we have to resort to a monotonicity argument
in G to estimate Gab by log N at the microscopic scale, which leads to the error bound √
log N
Np
. Bulk spectral universality: The local spectral statistics in the bulk coincide with those of
the GOE, i. they are asymptotically given by the Sine1 process. 3 26
6 General isotropic local law 42
7 Local spectral statistics: Proof of Theorem 1. 2 46
A Additional technical results and proofs 54
B Concentration for Markov jump processes 57
C A simple proof of average local law for GOE / GUE with factor √
log N 60
References 62
1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improve sparse random matrix analysis by implementing a Bernoulli flow method to establish local laws for sparse random matrices down to optimal spectral scales with optimal error bounds, replacing less effective Brownian characteristic flows when entries are not Gaussian.
-
Enhance delocalization characterization of eigenvectors in the bulk spectrum by utilizing anisotropic norms and showing that the bound on q(u) is improved by a factor 1 over N p in the direction of e, which captures constraints imposed by the top eigenvector u1.
-
Achieve local spectral universality for sparse random matrices by rigorously verifying loop equations using a third-order cumulant expansion controlled by the Bernoulli flow, enabling results down to the critical regime N p >= log N squared + kappa.
-
Develop a method for controlling quadratic variation of Dynkin martingales associated with observables using stochastic Grönwall estimates, allowing for the proof of local laws in Theorem 2.2 (i) and (ii) by showing that the stopping time τ equals T.
-
Extend delocalization results to directed Erdős-Rényi graphs by utilizing Hermitization techniques on non-Hermitian adjacency matrices and deriving bounds on left and right eigenvectors based on the uniform control of the local law for Hermitian counterparts.
-
Establish isotropic local laws for general vectors v, w in bulk spectra by defining isotropic observables φ iso vw,t with a set of vertices I and showing that the resulting stochastic Grönwall estimate controls these observables down to optimal scales.
-
Improve off-diagonal entrywise local laws by introducing a stopping time τ that captures the additional smallness due to off-diagonality, leading to a stochastic Grönwall estimate that proves τ equals T for the bulk spectrum.
-
Refine bounds on resolvent entries for non-Hermitian sparse matrices by showing that the off-diagonal component of the second order resolvent expansion term is bounded by a factor involving 1/(N p) in the desired way, improving upon previous bounds in (5.11).
Abstract
We study the eigenvalues and eigenvectors of the adjacency matrix A of the Erdős-Rényi graph G(N,p) in the regime Np much greater than (N) squared. We establish optimal isotropic delocalization for the bulk eigenvectors u, meaning that v, u squared at most C N over N with very high probability for any deterministic normalized v. In addition, we prove local spectral universality in the bulk by showing that the local spectral statistics coincide with those of the GOE. The main tool of our proof is a local law for the resolvent of A, down to optimal spectral scales and with optimal error bounds. Its proof relies on a new approach to local laws that we call the Bernoulli flow. It is a characteristic flow method in which the usual Brownian process is replaced by a Bernoulli process, where each edge of the graph forms an independent Markov process that jumps at unit rate from closed to open. The spectral parameter flows according to a suitably constructed matrix-valued Bernoulli characteristic flow.
Sources
- Loop Equations Characterize Random Matrix Statistics
- On a Rosenzweig-Porter-type model
- Universality of extremal eigenvalues of large random matrices
- Optimal Delocalization for Non--Hermitian Eigenvectors
- Delocalization of Non-Mean-Field Random Matrices in Dimensions $d\ge 3$
- Delocalization of Two-Dimensional Random Band Matrices
- The matrix Dyson equation and its applications for random matrices
- The Zigzag Strategy for Random Band Matrices
- Anomalous rate of eigenstate thermalisation at singularities of the density of states
- Localization-delocalization transition for a random block matrix model at the edge
- Almost-optimal bulk regularity conditions in the CLT for Wigner matrices
- On the localization length of finite-volume random block Schr\"odinger operators
- Delocalization of a general class of random block Schr\"odinger operators
- Delocalization of random band matrices at the edge
- Delocalization of One-Dimensional Random Band Matrices
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves