Eigenvalue spacings for regular graphs
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.