Maximum spectral sum of graphs

Abstract

For a graph $G$ of order $n$, the spectral sum of $G$ is defined to be the sum $\hat{I}{»}_1(G)+\hat{I}{»}_2(G)$, where $\hat{I}{»}_1(G)$ (resp. $\hat{I}{»}_2(G)$) is the largest (resp. second largest) adjacency eigenvalue of $G$. Ebrahimi, Mohar, Nikiforov and Ahmady (2008) conjectured that the spectral sum \[ λ_1(G) + λ_2(G)\le \frac{8}{7}n \] for any graph $G$. We prove this conjecture by combining tools from the theory of graph limits, convex geometry, exterior algebra and convex optimization. The techniques developed are of independent interest.

Minor corrections and updates