Local Kesten-McKay law for random regular graphs
Joint with Jiaohuang Huang ans Hong-Tzer Yau.
1. Motivation: quantum chaos
Consider billiard motion in a rectangle. It is a classically integrable system. The corresponding quantum problem consists in studying the Laplacian with Dirichlet boundary conditions. Eigenvalues can be explicitely computed. If square of ratio of sides is irrational, it is conjectured that
There are pretty close results (Sarnak). There are eigenfunctions which are localised near periodic orbits.
The Berry-Tabor conjecture is more general. In a hyperbolic rectangle, the classical dynamics is chaotic, the conjectured limit eigenvalue gap distribution is the eigenvalue gap distribution of a GOE matrix (standard Gaussian measure on space of symmetric matrices with inner product .
Bohigas-Giannoni-Schmit expect this to be true in general for chaotic systems.
The phenomenon of delocalised eigenfunctions is closely related.
It would be fun to study random surfaces, but hard. Therefore, we stick to graphs.
2. Random regular graphs
Let be the set of simple -regular graphs on vertices. Equivalently, of 0-1 symmetric matrices with rows summing to . Use uniform probability measure on , fix and let tend to infinity.
Locally, looks like a -tree up to radius , , i.e. -balls of all vertices have a bounded number of cycles, no cycles at all for most vertices.
This implies that normalized eigenfunctions cannot be localized: for any ,
(Brooks-Lindenstrauss, Dumitriu-Pal, Geisinger).
Note that in the GOE, with high probability,
which is much smaller. Our result gets closer to this bound, except for the highest eigenvalues.
Theorem 1 For , then with high probability,
for all eigenvectors with eigenvalue in .
3. Green function
I.e. resolvent , , , where . It allows to recover the spectral measure
and the eigenvectors: if , then
The Green’s function of the infinite tree is obtained by summing over walks, removing vertices ( becomes ), leading to a functional equation
and to the value
Le local tree-like structure gives that
for any fixed . It follows that the tends to an explicit law, th Kesten-McKay law.
4. Tree extension
Let us replace everything outside a ball of radius with trees. One gets a -regular graph, eventually polluted by a few cycles.
Main estimate. Simultaneously for every with large imaginary part, all vertices , , with high probability,
where is the tubular neighborhood of width of (empty if ). The idea is that the right-hand side is deterministic and locally computable.
5. Proof ideas
The main estimate is not too hard if , by direct expansion.
To access global structure, we resample boundaries of large balls (radius ). Simultaneous switching of all pairs outside balls that do not collide is measure preserving. So starting from random graph , this defines a new graph where the boundary gets random.
Use randomness of boundary to obtain two key improvements.
- Better decay of for distinct vertices of the boundary.
- Concentration estimate.