Strengthened upper bound on the third eigenvalue of graphs

Abstract

Let $G$ be a graph on $n\ge 3$ vertices, whose adjacency matrix has eigenvalues $\hat{I}{»}_1\ge \hat{I}{»}_2\ge \cdots \ge \hat{I}{»}_n$. The problem of bounding $\hat{I}{»}_k$ in terms of $n$ was first proposed by Hong and was studied by Nikiforov, who demonstrated strong upper and lower bounds for arbitrary $k$. Nikiforov also claimed a strengthened upper bound for $k\ge 3$, namely that $\frac{\hat{I}{»}_k}{n}<\frac{1}{2\sqrt{k-1}}-{\epsilon }_k$ for some positive ${\epsilon }_k$, but omitted the proof due to its length. In this paper, we give a proof of this bound for $k=3$. We achieve this by instead looking at $\hat{I}{»}_{n-1}+\hat{I}{»}_n$ and introducing a new graph operation which provides structure to minimising graphs, including $\ddot{I}‰\le 3$ and $\ddot{I}‡\le 4$. Then we reduce the hypothetical worst case to a graph that is $n/2$-regular and invariant under said operation. By considering a series of inequalities on the restricted eigenvector components, we prove that a sequence of graphs with $\frac{\hat{I}{»}_{n-1}+\hat{I}{»}_n}{n}$ converging to $-\frac{\sqrt{2}}{2}$ cannot exist.