Algebraic Graph Theory Seminar - Gabriel Coutinho

Monday, March 29, 2021 11:30 am - 11:30 am EDT (GMT -04:00)

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

Speaker: Gabriel Coutinho
Affiliation: Universidade Federal de Minas Gerais, Brazil
Zoom: Contact Soffia Arnadottir


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.