Title: The limits of the inertia bound
| Speaker: | Yuval Widgerson |
| Affiliation: | ETH Zürich |
| Location: | Please contact Sabrina Lato for Zoom link. |
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.