# 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 at the vertex and its neighbors:

the sum being over all neighbours of the vertex . There are 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 , the expected number of levels below . If, as usual, we unfold the sequence, then we get a sequence with mean spacing unity. Put . Then 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 -regular graphs. A graph is -regular if each vertex has exactly 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 , the eigenvalues of the generic -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 , , and large cyclic groups) where numerics suggest that the eigenvalue distribution is Poisson [ MR 2000g:05072]. Cayley graphs on are naturally thought of as discrete approximations to the spectral behaviour in the continuous setting of , 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.