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.

References and readings

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: