Algebraic Graph Theory Seminar - Sabrina Lato

Title: Linear Programming and Extremal Expanders

Abstract:

Nozaki proved a linear programming bound on the number of vertices that depends on the eigenvalues of a graph. Using this, he was able to show that any regular graph with girth at least twice the number of distinct eigenvalues minus one will be an extremal expander, or a k-regular graph on n vertices with second-largest eigenvalue minimal for all k-regular graphs graphs on n vertices. Consequentially, Moore graphs and triangle-free strongly regular graphs are examples of extremal expanders. This talk will give an overview of his results and the techniques used to prove them.