Notes of Roland Bauerschmidt’s Cambridge lecture 7-02-2017

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

\displaystyle  \begin{array}{rcl}  \frac{1}{N}\#\{j\leq N\,;\,\frac{\lambda_{j+1}-\lambda_j}{4\pi\mathrm{area}}\in[u,v]\}\rightarrow\int_u^v e^{-s}\,ds. \end{array}

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 {N\times N} matrices with inner product {Trace(XY)}.

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 {G_{N,d}} be the set of simple {d}-regular graphs on {N} vertices. Equivalently, of 0-1 {N\times N} symmetric matrices {A} with rows summing to {d}. Use uniform probability measure on {G_{N,d}}, fix {d} and let {N} tend to infinity.

Locally, {G_{N,d}} looks like a {d}-tree up to radius {R=c\log_d N}, {c<1}, i.e. {R}-balls of all vertices have a bounded number of cycles, no cycles at all for most vertices.

This implies that normalized eigenfunctions {v} cannot be localized: for any {d\geq 3},

\displaystyle  \begin{array}{rcl}  \|v\|_\infty =O(\frac{1}{\log_d N}). \end{array}

(Brooks-Lindenstrauss, Dumitriu-Pal, Geisinger).

Note that in the GOE, with high probability,

\displaystyle  \begin{array}{rcl}  \|v\|_\infty =O(\sqrt{\frac{\log N}{N}}), \end{array}

which is much smaller. Our result gets closer to this bound, except for the highest eigenvalues.

Theorem 1 For {d\geq 10^{40}}, then with high probability,

\displaystyle  \begin{array}{rcl}  \|v\|_\infty \leq \frac{(\log N)^{100}}{\sqrt{N}}. \end{array}

for all eigenvectors {v} with eigenvalue in {[-2\sqrt{d-1}+\epsilon,2\sqrt{d-1}-\epsilon]}.

3. Green function

I.e. resolvent {G(z)=(H-z)^{-1}}, {z\in{\mathbb C}}, {\Im(z)>0}, where {H=\frac{1}{\sqrt{d-1}}A}. It allows to recover the spectral measure

\displaystyle  \begin{array}{rcl}  \frac{1}{N}\Im Trace(G(E+i\eta) \end{array}

and the eigenvectors: if {Hv=Ev}, then

\displaystyle  \begin{array}{rcl}  \|v\|_\infty =\max_j \inf_{\eta>0}\sqrt{\eta\Im G_{ij}(E+i\eta)}. \end{array}

The Green’s function of the infinite tree is obtained by summing over walks, removing vertices ({G} becomes {G^{(i)}}), leading to a functional equation

\displaystyle  \begin{array}{rcl}  G_{jj}^{(i)}(z)=-\frac{1}{z+\frac{1}{d-1}\sum_{k\sim i}G_{kk}^{(j)}(z)}, \end{array}

and to the value

\displaystyle  \begin{array}{rcl}  G_{ii}(z)=m_d(z)=-\frac{1}{z+\frac{d}{d-1}m_{sc}(z)},\quad m_{sc}(z)=-\frac{1}{z+m_{sc}(z)}. \end{array}

Le local tree-like structure gives that

\displaystyle  \begin{array}{rcl}  \frac{1}{N}Trace G(z)\rightarrow m_d(z) \end{array}

for any fixed {z\in{\mathbb C}_+}. 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 {\ell} with trees. One gets a {d}-regular graph, eventually polluted by a few cycles.

Main estimate. Simultaneously for every {z} with large imaginary part, all vertices {i}, {j}, with high probability,

\displaystyle  \begin{array}{rcl}  G_{ij}(G,z)=G_{ij}(TE)+O(\log N)^{-c}, \end{array}

where {TE} is the tubular neighborhood of width {r=\log\log N} of {\{i,j\}} (empty if {d(i,j)>r}). The idea is that the right-hand side is deterministic and locally computable.

5. Proof ideas

The main estimate is not too hard if {\Im(z)\geq 2d}, by direct expansion.

To access global structure, we resample boundaries of large balls (radius {\log\log N}). Simultaneous switching of all pairs outside balls that do not collide is measure preserving. So starting from random graph {G}, this defines a new graph {\tilde G} where the boundary gets random.

Use randomness of boundary to obtain two key improvements.

  1. Better decay of {G_{ij}(\tilde G)} for distinct vertices of the boundary.
  2. Concentration estimate.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in seminar and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s