Algebraic Graph Theory Seminar - John Sinkovic

Title: Using eigenvalues to bound the independence number of a graph

Abstract:

Finding a maximum independent set (or clique) in an arbitrary graph has been shown to be NP-hard.  As any independent set gives a lower bound on the independence number, determining an upper bound is usually more useful.  Two such upper bounds are the Hoffman-Delsarte bound and the Cvetković bound.  Both use the eigenvalues of a matrix associated with the graph.  

I will introduce the two bounds and share some recent results from joint work with Zach Dockstader.