Friday, July 30, 2010
3:30 pm, MC 5158

Edwin van Dam
Tilburg University

Eigenvalues, polynomials, and structure in graphs

The eigenvalues of the adjacency matrix of a graph contain a lot --- but not always all --- information on the structure of the graph. We will review some structural properties that can be derived from the eigenvalues of a graph, and discuss when a graph is determined by its spectrum (of eigenvalues), or how different graphs with the same spectrum can be constructed.
We then dive deeper into graphs that have a lot of combinatorial symmetry: distance-regular graphs. We will see how systems of orthogonal polynomials can help to recognize such graphs from their eigenvalues and a little extra information. We apply this to obtain a recent characterization of the generalized odd graphs by their number of distinct eigenvalues and the length of their shortest odd cycles.
If time permits, we also show how eigenvalues led to the construction of the twisted Grassmann graphs, a family of distance-regular graphs that have the same spectrum as certain Grassmann graphs, but that are not vertex-transitive.