EIGENVALUE SPACINGS FOR REGULAR GRAPHS

DMITRY JAKOBSON, STEPHEN D. MILLER, IGOR RIVIN AND ZEÉV RUDNICK

Abstract. We carry out a numerical study of fluctuations in the spectra of regular graphs. Our experiments indicate that the level spacing distribution of a generic k-regular graph approaches that of the Gaussian Orthogonal Ensemble of random matrix theory as we increase the number of vertices. A review of the basic facts on graphs and their spectra is included.

1. Introduction

A regular graph is a combinatorial structure consisting of a set V of |V | vertices, connected by edges. Two vertices are called neighbors if they are connected by an edge; the graph is k-regular if each vertex has exactly k neighbors. To such a graph one associates 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 a vertex and its neighbors:

Δf(x) = kf(x) − ∑_{y∼x} f(y)

the sum being over all neighbors of the vertex x. The |V | eigenvalues 0 = E_{0} ≤ E_{1} ≤ ⋯ ≤ E_{|V |−1} lie in the interval between 0 and 2k. If we take a sequence of graphs with the number of vertices |V | → ∞, then under certain conditions (see Section 2) there is a limiting density of states analogous to Weyl’s law. This gives a mean counting function N̄(E), the expected number of levels below E, which we can use to measure the fluctuation properties of the eigenvalues in a large graph. If we “unfold” the sequence of eigenvalues (for instance by setting Ê_{j} = N̄(E_{j})), then we get a sequence Ê_{j} with mean spacing unity: s_{j} := Ê_{j+1} − Ê_{j} ∼ 1. The distribution function of the spacings \{s_{i}\} – P_{N}(s) = \frac{1}{N} ∑ δ(s − s_{i}) – is called the level spacing distribution of the graph. It is one of several quantities used to

Date: May 5, 1997.

1991 Mathematics Subject Classification. 81Q50, 15A18, 05C80, 15A52.

Key words and phrases. regular graphs, graph spectra, GOE, random matrices, quantum chaos.

2 JAKOBSON, MILLER, RIVIN AND RUDNICK

measure the statistical fluctuations of a spectrum. We wish to examine it in the limit as we increase the number of vertices to infinity.

Our motivation for studying these spectral fluctuations comes from the theory of Quantum Chaos, where one studies fluctuations of energy levels of dynamical systems, for instance the spectrum of the Laplacian of a manifold (where the classical motion is the geodesic flow). It has been conjectured that generically there is a remarkable dichotomy:

1. If the classical dynamics are completely integrable, then Berry and Tabor [2] conjectured that the fluctuations are the same as those of an uncorrelated sequence of levels, and in particular P (s) = e^{−s} is Poissonian.

2. If the classical dynamics are chaotic then Bohigas, Giannoni and Schmit [4], [5] conjectured that the fluctuations are modeled by the eigenvalues of a large random symmetric matrix - the Gaussian Orthogonal Ensemble (GOE)^{1}.

That is, the statistics of the spectral fluctuations are universal in each of the two classes.

While some obvious counter-examples exist, such as the sphere in the integrable case (the levels are k(k + 1) with multiplicity 2k + 1), and more subtle examples in the chaotic case, such as the modular surface (the quotient of the upper halfplane by the modular group SL(2, Z)), where the spacings appear to be Poissonian [1], [6], [14], [7], there is sufficient numerical evidence for us to believe that these universality conjectures hold in the generic case.

In the hope of gaining some extra insight into this matter we checked fluctuation properties of the spectrum of a regular graph. Graphs, for us, will occupy an intermediate step between quantizations of genuine chaotic dynamical systems and the statistical models of Random Matrix Theory. While we have no direct interpretation of graphs in terms of classical mechanics, an analogy is the random walk on a graph: Starting with an initial probability distribution, a particle at a given vertex moves to one its its neighbors with equal probability. This substitute for dynamics is chaotic in the following sense: The walk is recurrent if the graph is connected (which we interpret as ergodicity), and in that case is mixing if the graph is not bipartite. In the bipartite case, the set of vertices is a union of two

1Assuming the dynamics are invariant under time reversal.

EIGENVALUE SPACINGS FOR REGULAR GRAPHS 3

disjoint sets (inputs and outputs) so that inputs can only be connected to outputs and vice-versa. Thus if we start from an input vertex and walk any even number of steps then we will only be able to land on another input, never on an output.

There are examples (such as some Cayley graphs, see [3], [13]) where there are systematic multiplicities in the spectrum and the level spacing distribution at best exists only in some singular limit. For instance in the case of Cayley graphs of the cyclic group Z/nZ the appropriate limit gives a rigid spectrum: Ê_{n} = n, so that P (s) = δ(s−1) is a Dirac delta function. Another special example, analogous to the modular surface, seems to have Poisson spacings (numerical evidence by Lafferty and Rockmore [12]). These examples have certain symmetries or degeneracies. We tested a number of families of generic (pseudo)-random k-regular graphs (see section 4 for the details of the generation algorithm). The numerical evidence we accumulated, described in Section 5, indicates that the resulting family of graphs have GOE spacings. This should be compared with the numerical investigations by Evangelou [9] which indicate that in the case of sparse random symmetric matrices the spacings are GOE. We are thus led to conjecture that for a fixed degree k ≥ 3, the eigenvalues of the generic k-regular graph on a large number of vertices have fluctuations which tend to those of GOE (see Section 5 for a more precise statement).

The purpose of our paper is not only to describe our experimental results, but also to give a brief survey of the theory of Quantum Chaos for graph theorists, and of a bit of relevant graph theory for experts in Quantum Chaos. Accordingly, we included a survey of background material on graphs and their spectra in Section 2 , and a brief overview of Random Matrix Theory in Section 3. In section 4 we present the method used for generating graphs, and in section 5 the results of our experiments.

Acknowledgements. We thank N. Alon, M. Krivelevich, P. Sarnak and B. Sudakov for helpful conversations, and A. Odlyzko for providing routines to aid in the numerical computation of the GOE distribution. The work was partially supported by grants from the NSF, the US-Israel Binational Science Foundation and the Israel Science Foundation. D.J. was supported by an NSF postdoctoral fellowship and S.M. by an NSF graduate fellowhip.

4 JAKOBSON, MILLER, RIVIN AND RUDNICK

2. Graphs and their spectra

A graph G consists of a set V of vertices and a set E of edges connecting pairs of vertices. Two vertices v and w are called adjacent or neighboring (denoted v ∼ w) if they are joined by an edge. An ordering (v, w) of the endpoints of an edge e gives e an orientation; the second vertex is often called the head of e (denoted e_{+}), the first one is called the tail (denoted e_{−}). A graph G is directed if every edge of G is given an orientation. We shall mostly consider undirected graphs, where orientations are not specified.

Several edges connecting the same two vertices are called multiple edges; a graph with multiple edges is sometimes called a multigraph^{2}. An edge with coinciding endpoints is called a loop; we shall generally consider graphs without loops or multiple edges. The degree (or valency) of a vertex is the number of edges meeting at that vertex; G is called k-regular if the degree of every vertex is equal to k. A walk in G is a sequence (v_{0}, v_{1}, …, v_{s}) of vertices such that v_{i} ∼ v_{i+1}; it is closed if v_{0} = v_{s}. G is connected if every two vertices can be joined by a walk.

Associated to every graph is its adjacency matrix A. It is a square matrix of size n = |V | whose (i, j)-th entry is equal to the number of edges joining vertices v_{i} and v_{j} of G. For loopless graphs the diagonal entries of A are zero. The Laplacian Δ is an operator acting on functions on the set of vertices of G. It is defined by

(Δf)(v) = ∑_{w∼v}(f(v) − f(w)) (2.1)

Denote by B the diagonal matrix whose i-th entry is the degree of v_{i}; then

Δ = B − A

For regular graphs this gives Δ = k · Id − A (2.2)

To motivate the analogy with the Laplace-Beltrami operator on Riemannian manifolds, we first define the incidence mapping D. To do that, orient all edges of G in some way. D maps functions on the set of vertices to functions on the set of edges by the formula

Df(e) = f(e_{+}) − f(e_{−})

2The terminology varies: occasionally what we call a graph is called a simple graph, while what we call a multigraph is simply called a graph.

EIGENVALUE SPACINGS FOR REGULAR GRAPHS 5

If |V | = n and |E| = m, the matrix of D (called the incidence matrix) is an n-by-m matrix whose elements are 0 and ±1; D_{ij} = +1 if v_{i} is the head of e_{j}, to −1 if it is the tail and to 0 otherwise. The Laplacian matrix satisfies

Δ = DD^{t}. (2.3)

One may consider the set E of all directed edges (|E| = 2|E|) and think of directed edges one of whose endpoints is v as a tangent space to G at v; D can then be interpreted as a combinatorial analog of exterior differentiation d. The adjoint D^{∗} of D acts on functions g : E → R by

D^{∗}g(v) = ∑_{e∈E:e_{+}=v} g(e)

Then Δ = D^{∗}D, analogously to Δ = d^{∗}d on manifolds.

The Laplacian is a non-negative and self-adjoint operator. A constant function on a connected component of G is an eigenfunction of Δ with eigenvalue 0; the multiplicity of 0 is equal to the number of the connected components of G (exactly as for the manifold Laplacian). In the sequel we will only deal with connected graphs. The spectrum of A(G) for a k-regular graph G is clearly contained in [−k, k]; the spectrum of Δ(G) is contained in [0, 2k]. A graph is bipartite if the set V can be partitioned into disjoint subsets V = V_{1} ∪ V_{2} such that all edges have one endpoint in V_{1} and another in V_{2}. A k-regular graph is bipartite if and only if 2k is an eigenvalue of Δ, and in that case the spectrum of Δ has the symmetry E ↦ 2k − E. Indeed, let G be a bipartite graph and f be an eigenfunction of Δ(G) with eigenvalue E. Then let f′(v) be defined as follows:

f′(v) = \begin{cases}f(v), & v ∈ V_{1} \\ −f(v), & v ∈ V_{2} \end{cases}

It is not hard to check that f′ is an eigenfunction of Δ(G) with eigenvalue 2k − E. Denote the eigenvalues of the adjacency matrix A(G) of a k-regular graph G by

k = λ_{1} > λ_{2} ≥ … ≥ λ_{n} ≥ −k

The (i, j)-th entry of the matrix A^{r} is equal to the number of walks of length r starting at the vertex v_{i} and ending at v_{j}. Accordingly, the trace of A^{r} is equal to the number of closed walks of length r. On the other hand, tr(A^{r}) = ∑_{i=1}^{n} λ_{i}^{r} is

6 JAKOBSON, MILLER, RIVIN AND RUDNICK

(by definition) equal to n times the r-th moment of the spectral density

\frac{1}{n} ∑_{i=1}^{n} δ(x − λ_{i}) (2.4)

of A.

A closed walk (v_{0}, v_{1}, …, v_{r}) is called a cycle if v_{1}, …, v_{r} are distinct. The girth γ(G) of G is the length of the shortest cycle of G; all closed walks of length less than γ(G) necessarily involve backtracking (i.e. v_{i+1} = v_{i−1} for some i). The number of closed walks of (necessarily even) length 2r < γ starting and ending at any vertex v of a k-regular graph G is equal to the number of such closed walks starting and ending at any vertex of the infinite k-regular tree T_{k}.

We denote by G_{n,k} the set of k-regular graphs with n vertices. It is known [18] (and not hard to see) that for any fixed r ≥ 3 the expected number c_{r}(G) of rcycles in a regular graph G ∈ G_{n,k} approaches a constant as n → ∞; accordingly, for “most” graphs G ∈ G_{n,k} c_{r}(G)/n → 0 as n → ∞.

It is easy to show ([15, Lemma 2.2]) that the last condition implies that for each fixed r and for most graphs G ∈ G_{n,k} the average number of closed walks of length r on G is asymptotic to that of the tree. Accordingly, the r-th moments of the spectral density (2.4) approach those of the spectral density of the of the infinite k-regular tree T_{k} as n → ∞.

It follows ([15]) that the spectral density (2.4) for a general G ∈ G_{n,k} converges to the tree density ([11]) given by

f_{k}(x) = \{ \frac{k(4(k − 1) − x^{2})^{1/2}}{2π(k^{2} − x^{2})} ; 0 \begin{matrix}|x| ≤ 2\sqrt{k − 1} \\ |x| > 2\sqrt{k − 1} \end{matrix} (2.5)

supported in I_{k} = [−2\sqrt{k − 1}, 2\sqrt{k − 1}]. We refer to (2.5) as McKay’s law. It can be regarded as an analog for graphs of Weyl’s law for manifolds, in that both give limiting distributions for spectral densities.

3. Random Matrix Theory

We give a brief overview of the Gaussian Orthogonal Ensemble (GOE) of Random Matrix Theory^{3} - the statistical model relevant to graphs. It is the space of N × N real symmetric matrices H = (H_{ij}) with a probability measure P (H)dH which satisfies

3The standard reference is Mehta’s book [16].

EIGENVALUE SPACINGS FOR REGULAR GRAPHS 7

1. P (H)dH is invariant under all orthogonal changes of basis:

P (XHX^{−1})dH = P (H)dH, X ∈ O(N)

2. Different matrix elements are statistically independent. These requirements force P to be of the form

P (H) = exp(−a tr(H)^{2} + b tr(H) + c)

for suitable constants a > 0, b, c. After shifting the origin and normalizing one finds that the joint probability distribution of the eigenvalues λ_{j}, j = 1, …, N of H is given by

P_{N}(λ_{1} …, λ_{N})dλ = C_{N} ∏_{i<j}|λ_{i} − λ_{j}| exp(− ∑_{j} λ_{j}^{2}) ∏_{j=1}^{N} dλ_{j}. (3.1)

There is an expected limiting density for the eigenvalues of a large N × N matrix as N → ∞, given by Wigner’s semi-circle law:

R_{1}(x) = \begin{cases}\frac{1}{π} \sqrt{2N − x^{2}}, & |x| ≤ \sqrt{2N} \\ 0, & |x| > \sqrt{2N} \end{cases} (3.2)

Near the top of the semi-circle, at x = 0, the density is \sqrt{2N}/π. Thus if we “unfold” the eigenvalues by setting x_{j} := λ_{j}\sqrt{2N}/π, we will get a sequence of numbers \{x_{j}\} whose mean spacing is unity, as N → ∞.

RMT studies spectral fluctuation of the unfolded spectrum {x_{j}} as N → ∞, such as the probability distribution of the nearest neighbor spacing s_{n} := x_{n+1} − x_{n}. For each N × N matrix H, form the probability measure

p(s, H) = \frac{1}{N} ∑_{n=1}^{N} δ(s − s_{n})

Then as N → ∞, there is an expected limiting distribution (called the level spacing distribution) given by

P (s) = lim_{N→∞} ∫ p(s, H)P (H)dH

called the level spacing distribution. It was expressed by Gaudin and Mehta in terms of a Fredholm determinant. For small s, P (s) ∼ \frac{π^{2}}{6} s.

An approximation derived by Wigner before the Gaudin-Mehta formula was known, on basis of the N = 2 case, is the Wigner surmise

P_{W} (s) = \frac{π}{2} se^{−πs^{2}/4}

which gives a surprisingly good fit (see [16], Figure 1.5).

8 JAKOBSON, MILLER, RIVIN AND RUDNICK

It is worth emphasizing that the utility of RMT lies in that the predicted level spacing distribution P (s) and correlation functions are model-independent and appear in many instances, both probabilistic and deterministic, independent of features such as the level density (3.2). For instance, numerical studies indicate that sparse random matrices have GOE spacings [9], and the experiments described in the following section indicate that the same is true for eigenvalues of random regular graphs.

4. Random graph generation

We generated random k-regular graphs using a method described in [19]. It is easy to implement and extremely efficient for the small (≤ 6) values of k of current interest to us. On the other hand, the running time of the algorithm grows exponentially with the degree k, and (at least in our implementation) was found impractical for k > 7 on the hardware^{4} which we used. It should be noted that in the same paper [19], Wormald describes an algorithm which scales well with k, but is much more cumbersome to implement and slower for small k.

Wormald’s algorithm is easiest explained in terms of generating random bipartite graphs with prescribed vertex degrees. Assume that we wish to generate a random bipartite graph G with M_{b} blue vertices, named b_{1}, …, b_{M_{b}}, and M_{r} red vertices, named r_{1}, …, r_{M_{r}}. We would like the vertex b_{i} to have degree v_{i}, while the vertex r_{j} to have degree w_{j}. Evidently, we must have ∑_{i} v_{i} = ∑_{j} w_{j} = |E(G)|.

We now construct an array A of size |E(G)|. The first w_{1} cells of A contain r_{1}, the next w_{2} contain r_{2}, and so on. Now, we permute the E(G) cells of A by a random permutation in S_{E(G)}, to get another array A′. The array A′ defines a bipartite (multi)graph G′ as follows: The neighbors of b_{1} are the first v_{1} entries of A′, the neighbors of b_{2} are the next v_{2} entries, and so on. It is possible that G′ is a multigraph, since two of the neighbors of some b_{i} might well be the same. If that turns out to be the case, we scrap A′, and generate another random permutation, and thus another random array A′′, and corresponding multigraph G′′, and so on, until we have a true bipartite graph. It is clear that if the valences v_{i} and v_{j} are small, this process has a good chance of converging in reasonable time, and it should

4A 100Mhz Pentium processor PC running Linux.

EIGENVALUE SPACINGS FOR REGULAR GRAPHS 9

also be intuitively fairly clear that each bipartite graph with prescribed degrees is equally likely to appear. Both statements are proved in [19].

The problem of generating a random k-regular graph can, in effect, be reduced to the previous problem of generating a random bipartite graph. To wit, to each graph G we associate a bipartite graph B_{G}, such that V (B_{G}) = V (G) ∪ E(G), where the blue vertices of B_{G} correspond to the vertices of G, while the red vertices correspond to the edges of G. A vertex v is connected to e in B_{G}, whenever e is incident to v in G. A k-regular G gives rise to a graph B_{G}, where the blue vertices have degree k, while the red vertices have degree 2. On the other hand, not every bipartite H with degrees as above arises as B_{G} for some k-regular graph G, since if H has two red vertices r_{1} and r_{2} such that the blue neighbors of r_{1} are the same as those of r_{2}, the corresponding G is, in actuality, a multigraph.

The algorithm can thus be summarized as follows: To generate a random kregular graph with n vertices, first generate a random bipartite graph H with n blue vertices of degree k and nk/2 vertices of degree 2. If H = B_{G} for some (obviously unique) graph G, then return G, else try again. The expected running time of this process is analyzed, and the uniformity of the results is proved in [19].

Remark. Evidently, this method is even better suited to generating random bipartite graphs with a prescribed degree sequence. We have used the algorithm to generate random 3-regular and 5-regular bipartite graphs. The experimental results were not substantively different from those for general regular graphs (as described below).

5. Experimental results

We computed the eigenvalues of graphs generated as above. The spectral densities of a couple of families – one of 3-regular graphs and another of 5-regular graphs – are displayed in Figures 1(a) and 1(b) against McKay’s law (2.5).

(a) cubic graph on 2000 vertices; (b) 5-valent graph on 500 vertices. Figure 1. Eigenvalue distributions of random graphs vs McKay’s law

We then unfolded the spectrum by using McKay’s law, and computed the level spacing distribution. The resulting plots compared with GOE showed a good fit – see Figure 2.

Figure 2. Level spacing distribution of a cubic graph on 2000 vertices vs GOE

We tested the matter further by using a variant of the Kolmogorov-Smirnov test. One compares an empirical, sample distribution to an expected answer by measuring the deviation of the cumulative distribution functions of the two. Recall that if s_{i}, i = 1, …, N are random variables (the spacings, in our case), the empirical distribution function is P_{N}(s) = \frac{1}{N} ∑_{i=1}^{N} δ(s − s_{i}) and its cumulative distribution function is C_{N}(s) = \frac{1}{N} #\{i | s_{i} ≤ s\}. To test if the distribution function is given by a theoretical prediction F (s), define the discrepancy D(C_{N}, F) (or Kolmogorov-Smirnov statistic) to be the supremum of |C_{N}(s) − F (s)| over s > 0. The discrepancy is small if and only if the two distributions are close to each other. In the case that the s_{i} are independent, identically distributed (definitely not the case at hand!) with cumulative distribution function F (s), the discrepancy goes

EIGENVALUE SPACINGS FOR REGULAR GRAPHS 11

to zero almost surely as N → ∞ and there is a limit law giving the the limiting distribution L(z) of the normalized discrepancy \sqrt{N}D(C_{n}, F) as N → ∞:

L(z) := lim_{N→∞} P r\{\sqrt{N}D(C_{N}, F) ≤ z\} = ∑_{j=−∞}^{∞}(−1)^{j}e^{−2j^{2}z^{2}}

In the case that the s_{i}’s are spacings of uncorrelated levels (hence certainly not independent!), the level spacing distribution is exponential P (s) = e^{−s} as N → ∞ and Pyke [17] derives a limit law for the normalized discrepancy.

In the case where the s_{i}’s are spacings of certain models of RMT (not GOE, however), Katz and Sarnak [10] prove that the discrepancy goes to zero almost surely as N → ∞ and conjecture that there is a limit law as in the case of Kolmogorov-Smirnov and Pyke.

Miller (work in progress) has investigated this distribution for random symmetric and hermitian matrices and has numerically discovered that, after being normalized by multiplying by \sqrt{N}, it approaches a limiting distribution which seems independent of the type of matrix involved. In Figure 3 we show this cumulative distribution function L_{GOE}(z) of the normalized discrepancy for GOE (top plot) against the Kolmogorov-Smirnov “brownian bridge” L(z) (bottom plot) and Pyke’s distribution for spacings of uncorrelated levels (middle plot).

Figure 3. Cumulative distribution functions for normalized discrepancy. Top plot: GOE. Middle plot: Pyke’s limit law for spacings of uncorrelated levels.

Bottom plot: Kolmogorov-Smirnov limit law.

The numerical value of L_{GOE}(z) can be used as a goodness-of-fit test to see if the eigenvalues of a large symmetric matrix have GOE spacings in the same way one uses the Kolmogorov-Smirnov test.

We computed the discrepancy for the eigenvalues of a large number of random

graphs of particular types. Comparison of the normalized discrepancies to Miller’s

table gave good confidence that the spacings were indeed close to GOE. In Figure 4

we plot the distribution of the normalized discrepancies of a set of 4500 cubic graphs

on 300 vertices against Miller’s distribution (computed from a set of 5000 random

symmetric 120 × 120 matrices). As the figure indicates, the two distributions are

fairly close.

Figure 4. Distribution of normalized discrepancies for cubic graphs vs. GOE

Conclusion. The numerical evidence presented above leads us to believe that

for a fixed valency k ≥ 3, the eigenvalues of the generic k-regular graph on a

large number of vertices have GOE fluctuations in the sense that as we increase the

number N of vertices, for all but a vanishing fraction of these graphs the discrepancy

between the level spacing distribution of the graph and the GOE distribution goes

to zero.

References

1. R. Aurich and F. Steiner Energy-level statistics of the Hadamard-Gutzwiller ensemble, Physica D 43 (1990), 155–180.

2. M.V. Berry and M. Tabor Level clustering in the regular spectrum, Proc. Roy. Soc. London A356 (1977) 375–394.

3. N. Biggs Algebraic graph theory (Second Edition), Cambridge Univ. Press, 1993.

4. O. Bohigas, M.-J. Giannoni and C. Schmit, Phys. Rev. Lett. 52 (1984) 1.

5. O. Bohigas and M.-J. Giannoni Chaotic motion and Random Matrix Theories, Lecture Notes in Physics 209 (1984), 1–99, New York, Springer-Verlag.

6. E. Bogomolny, B. Georgeot, M.-J. Giannoni and C. Schmit Chaotic billiards generated by arithmetic groups, Phys. Rev. Lett. 69 (1992), 1477–1480.

7. E. Bogomolny, F. Leyvraz and C. Schmit Distribution of Eigenvalues for the Modular Group, Commun. Math. Phys. 176 (1996), 577–617.

8. B. Bollobás Random Graphs, Academic Press, London 1985.

9. S.N. Evangelou A Numerical Study of Sparse Random Matrices, Jour. Stat. Phys. 69 (1992), 361-383.

10. N. Katz and P. Sarnak The spacing distributions between zeros of zeta functions, preprint.

11. H. Kesten. Symmetric random walks on groups, Trans. AMS 92 (1959), 336–354.

12. J. Lafferty and D. Rockmore, private communication.

13. A. Lubotzky Discrete Groups, expanding graphs and invariant measures, Birkhauser, 1994.

14. W. Luo and P. Sarnak Number Variance for Arithmetic Hyperbolic Surfaces, Commun. Math. Phys. 161 (1994), 419–432.

15. B. McKay The expected eigenvalue distribution of a large regular graph, J. Lin. Alg. Appl 40 (1981), 203–216.

16. M.L. Mehta Random Matrices, Second Edition, Academic Press 1991.

17. R. Pyke Spacings (with discussion), J. Roy. Statis. Soc. B 27 (1965), 395–449.

18. N.C. Wormald The asymptotic distribution of short cycles in random regular graphs, J. Comb. Theo. B 31 (1981), 168–182.

19. N.C. Wormald Generating random regular graphs, Journal of Algorithms 5 (1984), 247-280.

Dept. of Mathematics 253-37, Caltech, Pasadena, CA 91125, USA

   E-mail address: jakobson@cco.caltech.edu

Department of Mathematics, Princeton University, Princeton NJ 08544, USA

   E-mail address: sdmiller@math.princeton.edu

Mathematics Institute, Warwick University, Coventry CV4 7AL, UK and Dept. of Mathematics 253-37, Caltech, Pasadena, CA 91125, USA

   E-mail address: rivin@caltech.edu

Raymond and Beverley Sackler School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel

   E-mail address: rudnick@math.tau.ac.il