Next: Gram matrices Up: The spectrum of a Previous: Graphs with largest eigenvalue

# The second largest eigenvalue of a regular graph

Let be a regular graph of valency on vertices, and assume that (for some real constant ) we have for all eigenvalues . The ratio determines randomness and expansion properties of : the smaller , the more random, and the better expander is.

For example, the following proposition says that most points have approximately the expected number of neighbours in a given subset of the vertex set.

Proposition 1.12.1   Let be a subset of size of the vertex set of . Then

Proof:     Apply interlacing to and the partition of .

An expander is a graph with the property that the number of points at distance at most one from any given (not too large) set is at least a fixed constant (larger than one) times the size of the given set. Expanders became famous because of their rôle in sorting networks (cf. Ajtai-Komlós-Szemerédi [1]) and have since found many other applications. The above proposition already implies that there cannot be too many vertices without neighbours in . A better bound was given by Tanner [32] (in order to show that generalized polygons are good expanders).

Proposition 1.12.2   (Tanner [32]) Let be a set of vertices of and let be the set of vertices adjacent to some point of . Then

where .

Proof:     Let be the characteristic vector of . Write it as a linear combination of a set of orthonormal eigenvectors of : where . Then and , so that . Now let be the characteristic vector of . Then , proving our claim.

Next: Gram matrices Up: The spectrum of a Previous: Graphs with largest eigenvalue
Andries Brouwer 2003-09-30