### Eigenvalue spacings for regular graphs

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

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 matrices, for all , of the form where has entries that have a standard normal distribution. Equivalently, an random symmetric matrix belongs to the GOE if the diagonal entries are independently randomly chosen with a distribution and the off-diagonal entries are independently randomly chosen with a 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.

### References and readings

- Dmitry Jakobson, Stephen D. Miller, Igor Rivin & Zeév Rudnick (2003) Eigenvalue spacings for regular graphs (eigenvalue_spacings_for_regular_graphs)
- GOE and Graphs
- Alan Edelman & N. Raj Rao (2005). Random matrix theory. Acta Numerica, 233-297. (random_matrix_theory)
- M.L. Mehta. Random Matrices, ThirdEdition, Academic Press 2004.