Combinatorics seminar
Speaker: Himanshu Gupta, University of Regina
Host: Niranjan Balachandran
Title: Expanders, Ramanujan Graphs, and Inverse Eigenvalue Problems for Graphs
Time, day and date: 10:00:00 AM - 11:00:00 AM, Thursday, March 26
Venue: Online (https://meet.google.com/cua-knbe-fzr)
Abstract: Spectral graph theory studies the relationship between the structure of a graph and the eigenvalues of matrices associated with it. Expanders are a special class of sparse yet highly connected graphs that play an important role in computer science and mathematics. The spectral gap quantifies expansion, and Ramanujan graphs are those achieving the optimal bound. In the first part of this talk, we discuss expanders, spectral gap, Ramanujan graphs, and spectra of Cayley graphs. We then turn to the family of graphs introduced by
Lazebnik and Ustimenko in 1995, which play a central role in extremal graph theory providing the best known examples for general lower bounds on the size of a graph for given order and girth. An important conjecture by Ustimenko asserts that this family of graphs is almost Ramanujan. We present recent progress on this conjecture in joint work with Taranchuk.
In the second part, we focus on the inverse eigenvalue problem for
graphs, which seeks to determine all spectra realizable by matrices whose off-diagonal zero/nonzero pattern matches edges/nonedges of a given graph. The Laplacian matrix of a graph is a fundamental object in combinatorics. We introduce the inverse eigenvalue problem for Laplacian matrices of a graph and present results on realizable spectra for several graph families, based on joint work with Catral, Fallat, and Lin.