🔢 mathematics

Bernoulli flow for Erd\H{o}s-Rényi graphs

This paper establishes optimal isotropic delocalization of bulk eigenvectors and local spectral universality for Erdős-Rényi graphs in the regime $Np \gg (\log N)^2$ by introducing a novel "Bernoulli flow" technique that replaces Brownian motion with a Bernoulli process to derive a sharp local law for the adjacency matrix resolvent.

Original authors: Joscha Henheik, Antti Knowles

Published 2026-09-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Joscha Henheik, Antti Knowles

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the study of complex systems, from the flow of electricity through a circuit to the behavior of particles in a quantum material, scientists often rely on a powerful mathematical tool: the random matrix. Imagine a vast grid of numbers where each entry is determined by chance. When these numbers are arranged into a square table, they form a matrix that can describe the energy levels of a physical system. A central question in this field is how the "waves" of energy, represented by the matrix's eigenvectors, spread out across the grid. In a healthy, conducting system, these waves are delocalized, meaning their energy is smeared evenly across the entire structure, allowing for free movement. In a broken or insulating system, the waves become localized, trapped in a tiny corner, unable to travel. Understanding the precise conditions under which a system switches from one state to the other is crucial for predicting how materials behave.

For decades, mathematicians have understood this behavior well when the connections in the system are dense and plentiful. However, a major mystery remained for systems that are sparse, where connections are few and far between. In these sparse networks, the randomness is so extreme that standard mathematical tools, which rely on smoothing out the noise, fail to work. The question was whether these sparse systems could still support the free flow of energy, or if they inevitably collapse into a trapped, localized state. The answer depends on a delicate balance: if the number of connections is too low, the system breaks; if it is high enough, the waves can still spread. Determining exactly where that line is drawn, and proving that the waves spread perfectly even in the sparsest possible cases, has been a significant challenge.

A team of researchers has now solved this problem for a specific type of sparse network known as an Erdős-Rényi graph. In this model, a network is built by connecting points with a certain probability, creating a web that is random but follows a clear statistical rule. The team focused on the regime where the average number of connections per point is large enough to keep the system alive, but still small enough to be considered sparse. They proved that in this regime, the energy waves are not just spread out, but are perfectly delocalized. This means that no matter which direction you look at the system, the energy is distributed as evenly as possible across all the points. Furthermore, they showed that the spacing between the energy levels in the middle of the system follows a universal pattern, identical to that found in the most random, idealized systems. This universality suggests that the specific details of how the network is built do not matter; the system behaves according to a fundamental law of nature.

To achieve this, the researchers had to invent a new mathematical method. Traditional approaches to studying these systems often involve imagining the network evolving over time, like a fluid flowing from a simple state to a complex one. This flow is usually modeled using a smooth, continuous process, similar to how a particle moves in a fluid. However, for sparse networks, this smooth approach fails because the randomness is too jagged and discrete. The team replaced this smooth flow with a new kind of process they call a "Bernoulli flow." Instead of a continuous drift, they imagined the network changing in sudden, discrete jumps. In this new model, every possible connection in the network acts like an independent switch that flips from off to on at a random moment. By tracking how the system's properties change as these switches flip, the researchers could follow the evolution of the network without losing control of the math.

This new method allowed them to bypass the difficulties that had blocked previous attempts. In the old methods, the researchers had to compare the sparse system to a smooth, Gaussian system, a step that introduced errors and made it impossible to reach the sparsest limits. The Bernoulli flow, by contrast, flows directly to the target distribution without needing a comparison. It is like navigating a rough, rocky terrain by stepping from stone to stone rather than trying to glide over it. The researchers found that as the network grows and more switches flip, the energy waves wash out the singularities caused by the few localized spots that might appear early on. By the time the network reaches its final state, the waves are completely delocalized.

The results are precise and rigorous. The team proved that as long as the average number of connections is greater than the square of the logarithm of the total number of points, the system exhibits optimal delocalization. This is a very low threshold, meaning the system remains conductive even when it is quite sparse. They also confirmed that the statistical pattern of the energy levels in the bulk of the system matches the Sine process, a signature of universal behavior found in many random systems. This finding is significant because it shows that the transition from a localized to a delocalized state happens much earlier than previously thought possible, and that the universal laws of random matrices hold true even in these very sparse, disconnected environments.

The work also extends to directed networks, where connections have a specific direction, such as one-way streets in a city. The researchers showed that the same rules of delocalization apply to these systems as well. Their method is flexible enough to handle networks with different connection probabilities and varying structures, suggesting that the Bernoulli flow could become a standard tool for analyzing a wide range of complex, sparse systems. By replacing the smooth, continuous flow with a discrete, jumping process, they have opened a new path for understanding how order emerges from chaos in the sparsest of networks. The proof relies on very high probability estimates, ensuring that the results hold true for almost every possible realization of the random graph, leaving no room for doubt about the behavior of these systems in the bulk.

Technical Summary: Bernoulli flow for Erdős-Rényi graphs

Problem Statement
This paper investigates the spectral properties of the adjacency matrix $A$ of the Erdős-Rényi random graph $G(N, p)$ in the sparse regime where $Np \gg (\log N)^2$ . Specifically, the authors study the normalized adjacency matrix $H = \theta A$ , where $\theta = (Np(1-p))^{-1/2}$ , to establish two hallmarks of the delocalized phase in the bulk spectrum:

Optimal Isotropic Delocalization: Proving that bulk eigenvectors $u$ satisfy $\langle v, u \rangle^2 \leq C \frac{\log N}{N} \|v\|_e^2$ for any deterministic normalized vector $v$ , where $\|\cdot\|_e$ is an anisotropic norm accounting for the near-alignment of the top eigenvector with the uniform vector $e$ .
Bulk Spectral Universality: Proving that the local spectral statistics in the bulk coincide with those of the Gaussian Orthogonal Ensemble (GOE), specifically converging to the Sine $_1$ point process.

The regime $Np \gg (\log N)^2$ is critical; while delocalization is known to hold down to $Np \gg \log N$ , the optimal bounds and universality were previously established only for denser graphs (e.g., $Np \geq N^\epsilon$ ).

Methodology: The Bernoulli Flow
The central technical innovation of this work is the development of a "Bernoulli flow," a new approach to proving local laws for sparse random matrices. This method adapts Pastur's method of characteristics, traditionally used with Brownian motion, by replacing the Brownian process with a Bernoulli process.

The Bernoulli Process: Instead of a continuous diffusion, the graph edges evolve via a Markov jump process where each edge jumps independently from closed (0) to open (1) at unit rate. At time $T$ , the edge probability is $p_T = 1 - e^{-T} = p$ .
The Bernoulli Characteristic Flow: A deterministic, matrix-valued flow $z_t$ for the spectral parameter is constructed to satisfy a time-dependent Matrix Dyson Equation (MDE). This flow is designed such that the generator terms of the associated observables cancel out, allowing the propagation of local laws from a trivial initial state (empty graph) to the target state.
Martingale Analysis: Since the Itô formula is unavailable for jump processes, the authors utilize Dynkin martingales associated with the observables (resolvent entries and their squares). The proof relies on:
- Estimating the predictable quadratic variation of these martingales.
- Controlling the jump sizes of the observables.
- Applying a Burkholder-Davis-Gundy-type inequality for jump processes to establish high-probability bounds.
- Using a stochastic Grönwall inequality to show that the observables remain small throughout the flow.

A key feature of this approach is that it flows directly to the Bernoulli distribution without generating an intermediate Gaussian component. Consequently, it avoids the perturbative comparison arguments (e.g., cumulant expansions or zigzag strategies) typically required to remove the Gaussian noise introduced by Brownian flows, which often fail in the sparse regime due to large entry moments.

Key Contributions and Results

Optimal Local Law: The authors establish a local law for the resolvent $G(z) = (H-z)^{-1}$ down to optimal spectral scales $\text{Im } z \sim \frac{\log N}{N}$ with optimal error bounds.
- Isotropic Law: $|(G(z) - M(z))_{vw}| \lesssim \|v\|_e \|w\|_e \left( \sqrt{\frac{\log N}{N\eta}} + \sqrt{\frac{\log N}{Np}} \right)$ .
- Off-diagonal Improvement: For $a \neq b$ , the error bound improves by a factor of $1/\sqrt{Np}$ in the sparse term.
- Anisotropic Norm: The results utilize a refined norm $\|v\|_e$ that captures the suppression of eigenvector mass in the direction of the uniform vector $e$ by a factor of $1/Np$ .
Optimal Isotropic Delocalization (Theorem 1.1): As a direct consequence of the local law, the paper proves that for any bulk eigenvector $u$ and any deterministic $v$ , $\langle v, u \rangle^2 \leq C \frac{\log N}{N} \|v\|_e^2$ with very high probability. This improves upon previous results that only achieved bounds of the form $N^\epsilon/N$ or required $Np \geq N^\epsilon$ .
Bulk Spectral Universality (Theorem 1.2): By combining the new local law with recent results by Bourgade and Huang regarding loop equations, the authors prove that the local eigenvalue statistics converge to the Sine $_1$ process. This extends universality to the very sparse regime $(\log N)^{2+\kappa} \leq Np \leq N^{1-\kappa}$ .
Extension to Directed Graphs: The methodology is shown to apply to directed Erdős-Rényi graphs, proving optimal isotropic delocalization for their left and right eigenvectors.

Significance and Claims
The paper claims that the lower bound $Np \gg (\log N)^2$ is a natural barrier for their specific method, arising from the need to control the jump sizes of the Dynkin martingale to ensure sub-exponential tail decay in the concentration inequalities.

The significance of the work lies in:

Overcoming the Gaussian Comparison Hurdle: By using the Bernoulli flow, the authors bypass the need to compare sparse matrices to Gaussian ensembles, a step that is notoriously difficult in the sparse regime due to the mismatch in entry distributions.
Optimality: The results provide the first proof of optimal delocalization bounds (up to the $\log N$ factor) and bulk universality for sparse random matrices in the regime where $Np$ is polylogarithmic in $N$ .
Non-Perturbative Nature: The approach is not perturbative around a Gaussian law, making it suitable for general sparse random matrix models with arbitrary variance profiles and expectations.

The authors note that while delocalization is known to hold down to $Np \gg \log N$ , their specific techniques for optimal delocalization and universality currently require the slightly stronger condition $Np \gg (\log N)^2$ . They also identify the extension of these results to the spectral edge as a future challenge, requiring a nontrivial extension of the local law to control concentration around a random approximation of the edge location.

More like this