Himanshu Gupta, University of Regina

Description

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.

Location
Online
URL
Date
Thu, March 26, 2026
Start Time
10:00am-11:00am IST
Duration
1 hour
Priority
5-Medium
Access
Public
Updated
Mon, March 23, 2026 8:10am IST