Colloquium Schedule         Guidelines         Directions        

Thursday, November 13, 2014

Eigenvalues and distance-regularity of graphs

Edwin van Dam (Tilburg)

Abstract: The eigenvalues of the adjacency matrix of a graph contain a lot --- but not always all --- information onthe structure of the graph. In this talk, we will dive deeper into graphs that have a lot of combinatorial symmetry:distance-regular graphs (such as Hamming graphs and Johnson graphs). We will give an overview of whendistance-regularity is determined by the eigenvalues (and when it is not). We will see how systems of orthogonalpolynomials can help to recognize distance-regular graphs from their eigenvalues and a little extra information through the `spectral excess theorem'.

We then discuss how these methods and ideas led to the construction of the twisted Grassmann graphs, a family ofdistance-regular graphs that have the same spectrum as certain Grassmann graphs. These twisted graphs are currently the only known family of distance-regular graphs with unbounded diameter that are not vertex-transitive.

If time permits, we also present some more recent results, such as a characterization of the generalized odd graphs ('the odd-girth theorem'), and discuss some results on graphs that are `almost distance-regular', in particular how the latter can be used to construct non-isomorphic graphs with the same eigenvalues.

<<< previous talk
next talk >>>

Location :  Room 611 of the Hans Freudenthal building, formerly known as the Wiskunde/Maths building, (campus De Uithof) Budapestlaan 6, Utrecht.
Date and time : Thursday, November 13, 2014 15:30-16:30. The lecture is preceded by coffee, tea, and cookies from 15.00 to 15.30 hour in the same room.