Rutgers Discrete Mathematics Seminar

Title:Four Conjectures in Spectral Extremal Graph Theory

Speaker: Michael Tait, Carnegie Mellon

Date: Monday, November 21, 2016 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


We discuss how to prove four conjectures in extremal graph theory where the graph invariant being maximized is a function of the eigenvalues or eigenvectors of the adjacency matrix of the graph. Our most difficult result proves a conjecture of Boots and Royle from 1991: the planar graph of maximum spectral radius is the join of an edge and a path of length $n-2$. All of our proofs follow a similar template, and we will end the talk with several problems to which one might try to apply our method. This is joint work with Josh Tobin.