Title: Interlacing, independent sets, and the inertia bound
Abstract: Graphs encode the connections between objects in a set. Matrices associated with a graph can, through their spectral data, provide useful information about the graph. Some major topics in algebraic graph theory are graph isomorphism, independent sets, graph coloring, quantum walks, and the Colin de Verdiére invariant.
Independent sets (and cliques) give information about the structure of a graph. Determining whether a graph has an independent set of a given size can be difficult (NP-hard). In comparison, calculating eigenvalues of large matrices is (relatively) fast and easy. The Cvetkovic bound (or inertia bound) uses the eigenvalues of a matrix associated with the graph to give an upper bound on the size of an independent set. Various people have asked whether the bound is tight. I will explain why it’s not.