05C50 Online Seminar: Shivaramakrishna Pragada

Abstract: Extremization of graph eigenvalues and their sums is a well-studied problem in spectral graph theory. A useful approach is to reduce optimization over graphs of arbitrary order to optimization over weighted graphs of bounded order. In this talk, we discuss a finiteness theorem for an eigenvalue maximization problem involving weighted Seidel adjacency matrices. The extremal value is attained on a weighted graph whose order admits an explicit bound depending only on the number of leading eigenvalues in consideration.

The main focus will be the finite reduction, which combines the Ky Fan maximum principle, an orthogonality-preserving cloning argument, and Carathéodory’s theorem from convex geometry. As a consequence, for each fixed subspace dimension, the maximal relative projection constants stabilize at the maximal absolute projection constant once the ambient dimension is sufficiently large, answering a question of Basso.

We will also briefly outline the solution of the maximum spectral sum problem. The spectral sum of a graph, defined as the sum of its two largest adjacency eigenvalues, is at most 8/7 of its order, proving a conjecture of Ebrahimi, Mohar, Nikiforov and Ahmady. The proof combines graph limits and a related reduction to weighted graphs on at most six vertices with exterior algebra and matrix sum-of-squares techniques.