🔢 mathematics

Density of states of randomly sprinkled graphs

This paper introduces a model of randomly sprinkled graphs that bridges the Anderson model and site percolation, providing an Anderson-percolation representation of the spectrum, characterizing its support, deriving quantitative bounds on the integrated density of states, and analyzing the density of states in the sparse sprinkling regime.

Original authors: Antti Knowles, Steffen Polzer

Published 2026-09-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Antti Knowles, Steffen Polzer

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 city grid to the behavior of electrons in a disordered material, scientists often look at the "spectrum" of a system. This spectrum is essentially a map of all the possible energy levels or frequencies at which the system can vibrate or resonate. Imagine a guitar string: it has a specific set of notes it can play. A complex network, like a massive web of interconnected nodes, has a far more intricate set of possible notes. One of the most fundamental questions in this field is understanding how the shape and structure of that network determine its musical range. For simple, perfectly ordered structures, this map is well known. But for messy, random networks that look more like the tangled roots of a tree or the chaotic connections of a social network, the picture becomes incredibly difficult to see.

A new study by Antti Knowles and Steffen Polzer tackles this difficulty by investigating a specific way of building these messy networks. They start with a large, solid "core" graph, which represents a stable, underlying structure. Then, they perform a process they call "sprinkling." At every single point on this core, they independently attach a small, random cluster of new points and connections. Some points might get a tiny cluster of three new nodes; others might get nothing at all; and some might get a larger, more complex shape. This model is designed to mimic real-world phenomena, such as a quantum particle hopping through a crystal lattice that has been contaminated by random impurities, or a social network where a stable core of friends is constantly gaining new, loosely connected acquaintances. The researchers wanted to know: how does this random sprinkling change the overall "song" of the network? Does it create new notes, silence old ones, or simply blur the lines between them?

The authors developed a mathematical framework to track exactly how these random additions alter the network's energy spectrum. They discovered that the effect of the sprinkling is not a simple, uniform blur. Instead, it creates a competition between two opposing forces. On one hand, the attached clusters act like tuning forks. If a small cluster has a specific natural frequency, it can force the entire network to vibrate at that exact frequency, creating sharp, distinct peaks in the spectrum. These are called "tuning fork" eigenvalues, and they are relatively easy to predict because they depend only on the shape of the small attached pieces. However, the researchers focused their attention on the more subtle, hidden changes that remain after these obvious peaks are accounted for.

They found that the remaining part of the spectrum is governed by a deep connection between two seemingly unrelated concepts: the way disorder affects quantum particles and the way a network breaks apart when points are randomly removed. By translating their problem into this language, they were able to prove that the spectrum of the sprinkled graph is almost entirely determined by a specific set of rules involving the core graph and the random clusters. They showed that the "song" of the network is essentially a combination of the core's original notes, shifted and distorted by the random potential of the attached clusters. This allows them to predict exactly where the energy levels will appear and how dense they will be.

One of the most striking findings concerns what happens when the sprinkling is very sparse, meaning that only a tiny fraction of the core points receive any new attachments. In this regime, the researchers found that the attached clusters do not just add noise; they actively push the existing energy levels of the core graph away from their original positions. Depending on the specific shape of the attached cluster and the local environment, a particular frequency can either become a "source," attracting new energy levels and increasing the density of states, or a "sink," repelling them and creating a gap. This means that even a tiny amount of random sprinkling can significantly reshape the landscape of possible energies, creating new peaks or clearing out others in a very specific, predictable way.

The study also revealed that for certain types of large, regular networks, these random peaks take on a very specific shape known as a Cauchy peak. These are sharp, bell-shaped curves centered exactly on the natural frequencies of the attached clusters. The researchers demonstrated that as the underlying network becomes larger and more connected, these peaks become the dominant feature of the spectrum near the frequencies of the attached pieces. This provides a clear, quantitative picture of how local disorder propagates through a global structure.

Furthermore, the authors proved that the spectrum of these sprinkled graphs is almost always continuous, except for the specific, sharp peaks caused by the tuning forks. This is a crucial distinction because it tells us that while the random sprinkling creates sharp, isolated notes, the vast majority of the network's behavior is fluid and spread out, rather than locked into a rigid, discrete set of states. They also showed that the total number of energy levels tends to increase in regions where the attached clusters have many natural frequencies, confirming that the sprinkling generally adds complexity to the system.

The work provides a rigorous mathematical foundation for understanding disordered systems that were previously only studied through simulations or approximations. By establishing a precise link between the geometry of the attached clusters and the resulting spectrum, the researchers have given scientists a powerful tool to predict the behavior of complex networks without needing to simulate every single connection. Whether applied to the design of new quantum materials or the analysis of large-scale data networks, this model offers a clear path to understanding how small, random changes can fundamentally alter the character of a large, complex system. The study confirms that while randomness introduces chaos, it does so according to strict, discoverable laws that can be mapped and understood.

Technical Summary: Density of States of Randomly Sprinkled Graphs

1. Problem Statement and Motivation
The paper investigates the spectral properties, specifically the density of states (DOS), of a class of random graphs constructed by "sprinkling" smaller random graphs onto the vertices of a large "core" graph $\mathbb{G}$ . This model is designed to capture the qualitative structure of many observed graphs, which often consist of a macroscopic core with smaller attached subgraphs (e.g., the Karp–Sipser core of Erdős–Rényi graphs).

The model is motivated by two primary contexts:

Random Graph Theory: It generalizes structures like the Erdős–Rényi graph, where the complexity of the DOS often arises from the addition of attached graphs to a simpler core.
Quantum Disorder: It serves as a model for quantum disorder where the disorder arises not from random potentials on a lattice (as in the standard Anderson model) but from the random grafting of supplementary atoms or small graphs to the lattice vertices.

The central challenge is to characterize the limiting empirical eigenvalue measure (the DOS) of the adjacency matrix $A$ of the sprinkled graph $G$ as the volume $|V| \to \infty$ , particularly understanding how the sprinkling modifies the DOS of the core graph $\mathbb{G}$ .

2. Model Definition
Let $\mathbb{G}$ be a large finite (random or deterministic) graph with vertex set $\mathbb{V}$ . At each vertex $x \in \mathbb{V}$ , an independent and identically distributed (i.i.d.) random element $(G_x, \phi_x)$ is drawn, where $G_x$ is a finite random graph and $\phi_x \in \{0, 1\}^{V_x}$ is an indicator vector. The graph $G_x$ is attached to $x$ by connecting $x$ to every vertex $t \in V_x$ where $\phi_x(t) = 1$ . The resulting graph $G$ has vertex set $V = \mathbb{V} \cup \{(xt) : x \in \mathbb{V}, t \in V_x\}$ .

The authors analyze the limit of the expected empirical eigenvalue measure $\nu_N$ of $G_N$ as $N \to \infty$ using the Benjamini–Schramm convergence framework. They assume the core $\mathbb{G}_N$ converges to an infinite rooted graph $(\mathbb{G}, \mathbb{o})$ and show that the sprinkled graphs converge to a limit $(G, o)$ .

3. Methodology
The paper employs a combination of probabilistic graph theory, spectral theory, and operator theory. Key methodological tools include:

Anderson-Percolation Representation: The authors derive an exact algebraic correspondence in finite volume between the eigenvalues of the sprinkled graph and a family of Anderson Hamiltonians defined on a site-percolated subgraph of the core. Specifically, for an energy parameter $\lambda$ , the spectrum of the sprinkled graph (excluding "tuning fork" eigenvalues) is related to the spectrum of the operator $H_\lambda = B_\lambda + V_\lambda$ , where $B_\lambda$ is the adjacency matrix of the subgraph induced by vertices where the attached graph's resolvent is finite, and $V_\lambda$ is a random diagonal potential derived from the attached graphs.
Tuning Fork Decomposition: The DOS is decomposed into a "tuning fork" part ( $\nu_{TF}$ ), arising from eigenvectors supported entirely on the attached graphs (vanishing on the core), and a non-tuning fork part. The tuning fork contribution is explicitly calculated.
Stieltjes Transform and Expansion: For sparse sprinkling (small probability $p$ of attaching a non-empty graph), the authors expand the Stieltjes transform of the DOS in powers of $p$ . This involves differentiating the Stieltjes transform with respect to $p$ and using the Helffer–Sjöstrand formula to translate bounds on the transform into bounds on the measure.
Ergodic Theory: To establish the almost sure constancy of the spectrum and the support of the DOS, the authors utilize ergodicity arguments adapted to the biased distribution of the root in the limit graph.

4. Key Contributions and Results

Existence of the Limit: Theorem 2.1 establishes the existence of the infinite-volume limit of the sprinkled graphs in the local topology, explicitly constructing the limit measure $\nu$ .
Anderson-Percolation Representation: Theorem 2.5 provides a representation for the atoms of the DOS. It shows that the non-tuning fork contribution to an atom at $\lambda$ is proportional to the density of states of the Anderson-percolation Hamiltonian $H_\lambda$ at $\lambda$ . This connects the problem to both the Anderson model and site percolation.
Support of the DOS: Theorem 2.15 characterizes the support of the DOS, $\Sigma$ , for deterministic, vertex-transitive cores with symmetric interval spectra (e.g., $\mathbb{Z}^d$ , Bethe lattices). The support is given by:
$\Sigma = \{ \lambda \in \mathbb{R} : \mathbb{P}(\lambda + r(\lambda) \in \Sigma_0) > 0 \} \cup \mathcal{T}$
where $\Sigma_0$ is the support of the core's DOS, $r(\lambda)$ is a function derived from the attached graphs, and $\mathcal{T}$ is the set of tuning fork eigenvalues.
Concentration of Mass: Theorem 2.16 provides quantitative bounds on the integrated density of states. It demonstrates that the sprinkling increases the expected number of eigenvalues predominantly in intervals containing many zeros of the function $r(\lambda)$ (related to the eigenvalues of the attached graphs).
Sparse Sprinkling Expansion: In the regime of small $p$ $p$ , the authors derive an expansion $\hat{\nu} = \nu_0 + p\phi + p^2 R$ $\overset{ν}{^} = ν_{0} + pϕ + p^{2} R$ .
- The first-order term $\phi$ is generally a distribution of order at most one, not necessarily a signed measure.
- The paper identifies "sources" and "sinks": depending on the local density of the core and the attached graphs, sprinkling can either increase or decrease the local mass of the DOS near an eigenvalue of the attached graph.
- For large degrees in the core (e.g., $\mathbb{Z}^d$ or Bethe lattices with large $d$ ), the expansion reveals that the DOS develops Cauchy peaks centered at the eigenvalues of the attached graphs (Theorem 2.25).
Expansion around $p=1$ : Appendix B derives a similar expansion for the case where the sprinkling probability is close to 1, which corresponds to a non-trivial but explicitly solvable deterministic model.

5. Significance and Claims
The paper claims to provide a rigorous framework for understanding how local graph perturbations (sprinkling) affect global spectral properties.

Connection to Known Models: The work unifies the study of random graphs with the Anderson model and percolation theory, showing that the spectrum of a sprinkled graph can be understood through the lens of an Anderson Hamiltonian on a percolated subgraph.
Quantitative Bounds: Unlike previous qualitative studies, this work provides explicit upper and lower bounds on the DOS and its integrated version.
Mechanism of Spectral Modification: The paper elucidates the competing mechanisms of eigenvalue generation (near attached graph eigenvalues) and eigenvalue repulsion. It rigorously characterizes when an eigenvalue of an attached graph acts as a source (increasing local DOS) or a sink (decreasing local DOS).
Limitations: The authors note that the first-order correction $\phi$ in the sparse expansion is often a distribution rather than a measure, requiring test against smooth functions. They also acknowledge that while the adjacency matrix is the focus, the techniques are expected to apply to other matrices like the Laplacian.

The paper does not claim to solve the DOS for all random graph models (e.g., it explicitly excludes the standard Erdős–Rényi graph due to lack of independence between the core and attached graphs in that specific construction) but rather establishes a general model that captures the "core-plus-attachments" structure observed in many complex networks and disordered systems.

More like this