Editor’s note: This blogpost is roughly based on an in-class presentation I gave for a class on Anderson localization (Ma 191c) at Caltech, which was taught by Lingfu Zhang. The presentation was based on the 2013 paper Mean quantum percolation by Charles Bordenave, Arnab Sen, and Bálint Virág. I make no claim to originality in this blogpost.
Motivating question: What features of random graphs are captured by their adjacency matrices (which are necessarily random matrices) and their associated spectral measures?
I’m going to first give you results without formally defining things as I should, and then I’ll formally define what I mean by things like: expected spectral measure, spectral measure of the adjacency matrix, local convergence, unimodular random graph, etc. I’ll also remark that by training, I use the word Bienaymé tree to refer to what many other probabilists call Galton-Watson trees (or less precisely, branching processes.)
Let’s take some case studies.
Model 1: Bernoulli(p) percolation on
Consider Bernoulli(p) bond percolation on , so independently for each edge of , we delete an edge with probability and retain it with probability . Call the resulting random graph . For , is just , which has absolutely continuous spectral measure. In fact, where denotes the spectrum of the adjacency operator of . (Recall that for a bounded linear operator on some Hilbert space , we have that In fact, the corresponding spectral measure (called the Plancherel measure) is exactly the -fold convolution of the measure defined by the density
On the other hand, for , because all clusters are finite, the expected spectral measure of is some countable mixture of atomic measures. In other words, it is purely atomic.
For the two-dimensional case, at least, the expected spectral measure does indeed capture something about the phase diagram:
Remark: That they could show this for and not is probably not surprising to many in the field. Indeed, the proof uses the planar self-duality of , which obviously cannot be leveraged in high dimensions.
Model 2: The Erdős–Rényi graph
Consider the complete graph on vertices (so there is an edge between any two vertices in the ambient graph). An extremely well-studied random graph model is Bernoulli percolation on . We call the graph the Erdős–Rényi graph . Of course, this is often more interesting when we let be some function on .
What does the adjacency matrix look like? We can describe it quite well: because this graph has no self-loops, it’s 0 on the diagonal (), while off the diagonal , with . We should expect the operator norm of (the adjacency matrix of to be roughly .
So, if we look at the appropriately centred/normalized and rescaled matrices, so long as , we can use a universality result (Wigner’s semicircle law) and conclude that the distribution of the eigenvalues converges to the Wigner semicircular distribution which has density What about the sparse regime? That is, the regime where say and thus ? Here the connection probability decays in . In this case, the limiting expected spectral measure was already known to be quite different. It was known the limiting spectral measure was supported on all of . Recall by the Lebesgue-Radon-Nikodym theorem that any measure on decomposes into a pure-point part, a part which is absolutely continuous with respect to the Lebesgue measure, and a part which is atomless but singular with respect to the Lebesgue measure (I’ll call this the singular continuous part of the measure.) It was known that the pure-point of this spectral measure was supported on a dense set of atoms. Since the closure of a dense set of atoms is all of , it’s totally consistent for this measure to have no continuous part, but it’s also possible for this measure to have a continuous part.
It turns out the answer is exactly what you would hope it would be:
To most discrete probabilists, this isn’t too surprising. Indeed, if you study the largest component in , a classical theorem says that where is the survival probability of an Bienaymé tree.
(More can be shown: is exactly the critical theshold. For , there are multiple components; for , there is a unique giant component of linear size, meaning of size , while the other components are . At , the largest component is of size .)
In other words, , the expected spectral measure captures the phase transition that we observe in . But why is this true? From a local standpoint, for , a uniformly random root sees an Bienaymé tree. Intuitively, if we do breadth-first search of a component, what we see looks like a (unimodular) Bienaymé tree with offspring distribution . But random variables converge in total variation distance to random variables. In fact, you can show that there exists a coupling of , such that
It turns out that this analysis will follow by one last case study: (unimodular) Bienaymé trees.
Model 3: (Unimodular) Bienaymé trees
Fix a probability measure on with finite mean. The unimodular Bienaymé tree with offspring distribution can be described as follows: the root produces children according to , while every other vertex independently of the root and of each other reproduces according to , the size-biasing of . Here, the size-biasing of is defined by
What does the expected spectral measure look like?
Again we see that some kind of phase transition is captured by the spectral measure. Indeed, by the extinction criterion for (typical) Bienaymé trees (throwing away the degenerate-case that produces 1 child almost surely), a Bienaymé(Z) tree is infinite with positive probability if and only if .
But why are all of these results true, and how are they related?
Philosophy
The philosophy is that the spectral measure of a random graph is local. The reason why is that you can solve for the eigenvalues of the adjacency of a finite graph locally.
I’ve been thinking a lot about local and universal results recently. A notion of convergence is basically as useful as what properties are preserved under it. Sometimes, you want to understand things by understanding what universality class they live in. You might want to use Donsker’s theorem to understand centred random walks, Aldous’ theorem to understand the convergence of critical Bienaymé trees (conditioned to have size ) to the Brownian continuum random tree. You might want to understand the conformally-invariant scaling limits of 2-dimensional percolation interfaces. What connects these type of results is that that the local particularities wash out: for example, in the last example, it shouldn’t matter whether you study percolation on the triangular lattice or the square lattice. Or, for example, everything looks "degree 3" in the Brownian continuum random tree, but you can take an offspring distribution with mean that has and still the sequence will converge to the Brownian continuum random tree.
In other cases, though, you really do care about local information, and you should study what is preserved under local convergence. Some examples:
Take a sequence of vertex-transitive graphs which converge locally to a vertex-transitive graph . Suppose that , so these graphs aren’t one-dimensional. Then a 2023 theorem of Philip Easo and Tom Hutchcroft says that as . This was Schramm’s locality conjecture.
Eigenvalues and expected spectral measure. We’ll make sense of the following statement: let be a sequence of unimodular random graphs converging to a unimodular random graph . Then the expected spectral measure as measures, and if you additionally assume that are sofic, then that is, you get pointwise convergence of atoms.
What is this local convergence that I’m talking about? Let be the rooted graphs , up to rooted isomorphisms. (In other words, I quotient out.) Say that where is the largest integer such that , meaning the -neighbourhoods of the root are isomorphic. It turns out that this topology makes a nice Polish space, and once you have a notion of convergence on any Polish space, you can always define what it means for measures valued on to converge. To make it more explicit, say a sequence of random rooted graphs converges to iff for any finite graphs ,
One of the main insights of this paper is to study things at the level of unimodular random graphs (or equivalently, Borel pmp graphs). These objects arise naturally from many different models in discrete probability. Correctly normalized Bienaymé trees are examples of unimodular random graphs; the cluster of the origin in Bernoulli(p) percolation on a transitive graph also gives rise to a URG. Unimodular random graphs, even non-sofic ones, have a well-defined expected spectral measure; in fact this is not obvious, and one of the main technical results of Mean quantum percolation (see Proposition 1.4).