GOE and Graphs

To a graph one can associate a combinatorial Laplacian, which operates on functions on the vertices by giving the sum of the differences between the values of a function $f$ at the vertex and its neighbors:

\begin{displaymath}\Delta f(x)=\sum_{y\sim x}(f(x)-f(y)),\end{displaymath}

the sum being over all neighbours of the vertex $x$. There are $\vert V\vert$ eigenvalues. If we take a sequence of graphs such that the number of edges tends to infinity, then under certain conditions there is a limiting density of states analogous to Weyl's law. This gives a mean counting function ${\tilde N}(E)$, the expected number of levels below $E$. If, as usual, we unfold the sequence, then we get a sequence ${\tilde E_j}$ with mean spacing unity. Put $s_j:={\tilde E}_{j+1}-{\tilde E}_j$. Then $P_N(s)={1\over N} \sum \delta(s-s_i)$ is the distribution function of the spacings and is called the level spacing distribution of the graph.

A question that arises is to study the level spacing distribution of certain families of graphs. One such family is the family of $k$-regular graphs. A graph is $k$-regular if each vertex has exactly $k$ neighbours. For this family numerical evidence [1] indicates that the resulting family of graphs have GOE spacings. Indeed in [1] the authors conjecture that for fixed degree $k\ge 3$, the eigenvalues of the generic $k$-regular graph on a large number of vertices have fluctuations which tend to those of GOE.

On the other hand certain classes of graphs are known (for example 4-regular Cayley graphs on $SL_2(F_p)$, $S_{10}$, and large cyclic groups) where numerics suggest that the eigenvalue distribution is Poisson [ MR 2000g:05072]. Cayley graphs on $SL_2(F_p)$ are naturally thought of as discrete approximations to the spectral behaviour in the continuous setting of $SL_2(Z)\backslash H$, where computations indicate that the spacing distribution should be also Poisson. In all cases where the distribution seems to be Poisson, there are symmetries or degeneracies (eigenvalues occurring with a high multiplicity).

[1] D. Jakobson, S.D. Miller, I. Rivin and Z. Rudnick, Eigenvalue spacings for regular graphs, in Emerging applications of number theory.



Back to the main index for L-functions and Random Matrix Theory.