Algebraic Graph Theory Seminar - John Sinkovic

Thursday, September 14, 2017 3:30 pm - 3:30 pm EDT (GMT -04:00)

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

Speaker: John  Sinkovic
Affiliation: University of Waterloo
Location: MC 6486


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.