Tutte seminar - Sebi Cioaba

Recent developments in spectral graph theory

Abstract:

Spectral graph theory studies the connections between the structure of a graph and its eigenvalues. The most studied eigenvalues are the largest (related to regularity of graph and its chromatic number), the second largest (which shows if the graph is an expander) and the smallest (related to the independence number of a graph and also, measuring how bipartite the graph is). I will present some old and new connections between the spectrum of a graph and its structure and I will show that other eigenvalues contain relevant graph information as well.