Algebraic Graph Theory Seminar - Gabriel Coutinho

Title: Why are Hoffman's bounds for alpha and chi truly duals of each other?

Abstract:

Two of the most well known eigenvalue bounds for graph parameters look suspiciously related. Our goal in this talk is to confirm this suspicion by casting these bounds into a framework of semidefinite optimization that will give us almost for free a duality relation. As one should always expect in this context, we will see a connection to the Lovász theta function of a graph.