# Research in Scientific Computing in Undergraduate Education

### Eigenvalue spacings for regular graphs

A simple graph is k-regular if every vertex has degree $k$.

There are a number of matrices associated with a simple graph: in particular the incidence matrix and the combinatorial Laplacian matrix.

The eigenvalues of these matrices reflect combinatorial structure of the graph.

There is numerical evidence – see Jakobson et al (2003) below – that the eigenvalues of the combinatorial Laplacian matrix of k-regular graphs behave like the eigenvalues for the Gaussian Orthogonal  Ensemble, GOE. The GOE consists of symmetric $n\times n$ matrices, for all $n$, of the form $\frac{1}{2}(A + A^T )$ where $A$ has entries that have a standard normal distribution. Equivalently, an $n\times n$ random symmetric matrix belongs to the GOE if the diagonal entries are independently randomly chosen with a $N(0,1)$ distribution and the off-diagonal entries are independently randomly chosen with a $N(0,1/\sqrt(2))$ distribution (see section 3 of Jakobson et al (2005), section  4.3 of Edelman & Rao (2005), below, and Mehta (1991)).

The aim of this project is to explore this connection further, and to also consider the distribution and spacing of the eigenvalues of the normalized Laplacian matrix of a k-regular graph.