À¶Ý®ÊÓƵ

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 a²ÔÌýextremal expander, or a k-regular graph o²ÔÌý²ÔÌývertices with second-largest eigenvalue minimal for all k-regular graphs graphs o²ÔÌý²ÔÌý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.