Graph Eigenvalues and Projection Constants

Abstract

For an integer $k\ge 2$, let $\hat{I}{»}_k(G)$ denote the $k$th largest adjacency eigenvalue of a graph $G$. For every graph $G$ on $n$ vertices and every $2\le k\le n$, we prove \[ λ_k(G) \le \frac{(k-2)\sqrt{k+1}+2}{2k(k-1)}\,n-1. \] Our bound is tight for $k\in \{2,3,4,8,24\}$. We obtain it by reducing the graph-eigenvalue problem to an extremal problem for orthogonal projections and then applying the general upper bound on the absolute projection constant ${\hat{I}}^3(r)$ due to Deręgowska and Lewandowska. We also give an alternative proof of their bound by repairing the Gegenbauer-polynomial argument of König and Tomczak-Jaegermann. The resulting slack identity yields a strict improvement in every even dimension $r\ge 4$ for which $r+2$ is not a perfect square.

This paper combines and supersedes the manuscripts arXiv:2603.21181, arXiv:2603.28738, and arXiv:2603.29280, which will not be published separately, and includes additional results and improvements