Talk information

Date: Sunday, January 21, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Yuval Wigderson (ETH Zurich)
Title: Spectral bounds on the independence number

Abstract:

Spectral graph theory provides us with a wide array of surprising results which relate graph-theoretic parameters to linear-algebraic parameters of associated matrices. Among the most well-known and useful of these is Hoffman’s ratio bound, which gives an upper bound on the independence number of a graph in terms of its eigenvalues.

A closely related result is Cvetković’s inertia bound, another inequality relating the independence number and the eigenvalues of a graph. Despite its similarity to the ratio bound, the inertia bound is much less well-understood—until a few years ago, it was unknown whether this simple inequality is always an equality! In this talk, I will survey what is known about these two bounds, and will present a powerful new approach to answering such questions.

Joint work with Matthew Kwan.