Upper bound on the k k -th eigenvalue of a graph
Varun Sivashankar · 2026
Read Upper bound on the k k -th eigenvalue of a graph by Varun Sivashankar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-28738.txt.
Introduction
Sivashankar proves a general upper bound on the k-th adjacency eigenvalue of a graph. The bound applies to every graph on n vertices, for k at least two. He builds on a recent approach that handled the case k equal to three. Gegenbauer polynomial positivity extends the bound to all larger k. The bound is tight for k equal to 2, 3, 4, 8, and 24. Sivashankar also highlights a close link to questions about equiangular lines. The result connects spectral graph theory with a classic geometry problem.
Catalog record
| CREATOR | Varun Sivashankar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23658 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.28738
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Upper bound on the k k -th eigenvalue of a graph Thanks: Princeton University. Email: [email protected] . Varun Sivashankar Abstract . We prove a general upper bound on the k k -th adjacency eigenvalue of a graph. For k ≥ 2 k\geq 2 , we show that λ k ( G ) ≤ ( k − 2 ) k + 1 + 2 2 k ( k − 1 ) n − 1 \lambda_{k}(G)\leq\frac{(k-2)\sqrt{k+1}+2}{2k(k-1)}\,n-1 for every graph G G on n n vertices. We build on a recent approach that addresses the case k = 3 k=3 and generalize the upper bound for all k ≥ 3 k\geq 3 by using the positivity of Gegenbauer polynomials. The upper bound is tight for k ∈ { 2 , 3 , 4 , 8 , 24 } k\in\{2,3,4,8,24\} . We also highlight the close relation of λ k ( G ) \lambda_{k}(G) to questions about equiangular lines. 1. Introduction For a simple undirected graph G on n vertices, let \lambda_{1}(G)\geq\lambda_{2}(G)\geq\cdots\geq\lambda_{n}(G) denote the eigenvalues of its adjacency matrix. Following Nikiforov [ 19 ] , define c_{k}:=\sup\left\{\frac{\lambda_{k}(G)}{|V(G)|}:|V(G)|\geq k\right\}. The problem of bounding \lambda_{k}(G) in terms of the order of the graph goes back at least to work of Hong and Powers [ 9 , 10 , 20 ] . Nikiforov [ 19 ] proved the universal estimate c_{k}\leq\frac{1}{2\sqrt{k-1}}\qquad(k\geq 2), On the lower-bound side, the balanced complete k -partite graph gives c_{k}\geq 1/k , and Nikiforov showed that in fact c_{k}>1/k for every k\geq 5 [ 19 ] . He therefore asked whether c_{3}=1/3 and c_{4}=1/4 [ 19 , Question 2.11] . Powers had earlier proposed a conjecture that \lambda_{k}(G)\leq\lfloor\frac{n}{k}\rfloor for connected graphs, but Nikiforov later observed that the original proof is flawed; moreover, Nikiforov’s constructions show that this bound fails for every k\geq 5 , while Linz later ruled out the case k=4 [ 20 , 19 , 15 ] . The remaining case k=3 is also recorded in the survey of Liu and Ning [ 16 , Problem 10] . Recent work has clarified the first unresolved cases. Leonida and Li verified the sharp third-eigenvalue bound for several important graph classes and formulated a weighted matrix conjecture that would imply it in full generality [ 13 ] . See also Li [ 14 ] for a related asymptotic improvement on Nikiforov’s bound. Very recently, Tang proved the sharp inequality \lambda_{3}(G)\leq\frac{n}{3}-1 for every graph G by confirming the conjecture of Leonida and Li [ 24 ] . On the lower-bound side, it is easy to see that c_{3}\geq 1/3 by taking the disjoint union of three equal sized cliques. [ 19 ] proved that c_{k}>\frac{1}{2\sqrt{k-1}+1} when q is an odd prime power and k=q^{2}-q+1 . [ 19 ] also showed that c_{k}>\frac{1}{2\sqrt{k-1}+k^{1/3}} for sufficiently large k . Further, Linz provided several improved constructions for 4\leq k\leq 24 [ 15 ] . Our main result is the following. Theorem 1.1 . Let k\geq 2 be an integer. For every graph G on n vertices, \lambda_{k}(G)\leq\alpha_{k}n-1,\qquad\alpha_{k}:=\frac{(k-2)\sqrt{k+1}+2}{2k(k-1)} Consequently, c_{k}\leq\alpha_{k} For k=2 , this simply follows from the classical sharp bound \lambda_{2}(G)\leq n/2-1 [ 9 , 19 ] . Our result holds for k\geq 3 . For k=3 , it recovers Tang’s sharp bound \lambda_{3}(G)\leq n/3-1 [ 24 ] . For k\in\{4,8,24\} , \alpha_{k} matches Linz’s lower bound [ 15 ] . Therefore, our upper bound is tight for k\in\{2,3,4,8,24\} . It is very interesting to note that our upper bound for \lambda_{k}(G) is tight whenever an extremal equiangular lines configuration exists in dimension r=k-1 . We discuss this in further detail in Section 5.1 . For every k\geq 2 one has \alpha_{k}<\frac{1}{2\sqrt{k-1}} , so Theorem 1.1 improves Nikiforov’s universal bound for \lambda_{k}(G) . We remark that Nikiforov claimed that there exists a positive \epsilon_{k} such that c_{k}\leq\frac{1}{2\sqrt{k-1}}-\epsilon_{k} . However, the proof was omitted because it relied on the Removal Lemma of Alon, Fischer, Krivelevich, and Szegedy [ 1 ] with other tools of analytic graph theory. This would make the proof complicated and give a small \epsilon_{k} . Our proof follows the overall strategy of Tang [ 24 ] . As in their work, the graph-theoretic theorem is deduced from a weighted matrix inequality using the identity A(G)+A(\overline{G})=J-I and Weyl’s inequality. The key new modification is the use of Gegenbauer polynomials to generalize the trigonometric upper bound from the rank- 2 case. The required positive-kernel input goes back to Schoenberg [ 21 ] ; for related perspectives in spherical coding and semidefinite methods, see also Delsarte–Goethals–Seidel [ 6 ] and Bachoc–Vallentin [ 2 ] . 2. Positive Kernels Fix an integer r\geq 2 . Let S^{r-1}=\{v\in\mathbb{R}^{r}:\|v\|_{2}=1\} be the unit sphere. For real vectors u,v , let \langle u,v\rangle denote the standard inner product. For real valued square matrices A,B\in\mathbb{R}^{n\times n} , write \langle A,B\rangle_{F}=\tr(A^{T}B) for the Frobenius inner product. This is equivalent to just taking taking the inner product by viewing A and B as n^{2} -dimensional vectors. For a matrix, \|A\|_{F}=\sqrt{\langle A,A\rangle_{\!F}} and \|A\|_{1}=\sum_{i,j}|A_{ij}| . Let I_{r}\in\mathbb{R}^{r\times r} denote the identity matrix. A matrix M\in\mathbb{R}^{n\times n} is positive semidefinite if x^{\top}Mx\geq 0 for all x\in\mathbb{R}^{n} . Definition 2.1 . A function f:\mathbb{R}\rightarrow\mathbb{R} is positive semidefinite on S^{r-1} if for all unit vectors u_{1},\ldots,u_{n}\in S^{r-1} , the matrix M\in\mathbb{R}^{n\times n} given by M_{ij}=f(\langle u_{i},u_{j}\rangle) is positive semidefinite. Define f^{r}_{2}(t)=t^{2}-\frac{1}{r} f^{r}_{4}(t)=t^{4}-\frac{3}{r(r+2)} We will prove that f_{2}^{r} and f_{4}^{r} as positive semidefinite on S^{r-1} . In Section 3 , this will play a crucial role in bounding \|Q\|_{1} for a rank r orthogonal projection matrix Q\in\mathbb{R}^{n\times n} . Lemma 2.2 . For r\geq 2 , define \phi(u):=uu^{\top}-\frac{1}{r}I_{r},\qquad u\in S^{r-1}. Then for all u,v\in S^{r-1} , \langle\phi(u),\phi(v)\rangle_{\!F}=f_{2}^{r}(\langle u,v\rangle). Further, f_{2}^{r} is positive semidefinite on S^{r-1} . Proof. A direct computation gives \displaystyle\langle\phi(u),\phi(v)\rangle_{\!F} \displaystyle=\tr\!\left(\left(uu^{\top}-\frac{1}{r}I_{r}\right)\left(vv^{\top}-\frac{1}{r}I_{r}\right)\right) \displaystyle=(u^{\top}v)^{2}-\frac{1}{r}=\langle u,v\rangle^{2}-\frac{1}{r}=f_{2}^{r}(\langle u,v\rangle). Now observe that for any u_{1},\ldots,u_{n}\in S^{r-1} , the n\times n matrix (f_{2}^{r}(\langle u_{i},u_{j}\rangle))_{i,j=1}^{n} is just the Gram matrix of the matrices \phi(u_{1}),\ldots,\phi(u_{n}) with the standard Frobenius inner product. Therefore, it must be positive semidefinite. ∎ To prove that (f_{2}^{r}(\langle u_{i},u_{j}\rangle))_{i,j=1}^{n} is PSD, we expressed it as a Gram matrix of certain matrices with the Frobenius inner product. We will do the same thing for f_{4}^{r} , but since f_{4}^{r} is a degree 4 polynomial, we will need to work with 4 -tensors. The proof of Section 2 is elementary but requires some computation. We defer this proof to the appendix. Lemma 2.3 . For r\geq 2 , f_{4}^{r}(t)=t^{4}-\frac{3}{r(r+2)} is positive semidefinite on S^{r-1} . Remark 2.4 . Section 2 and Section 2 are just special cases of a theorem by Schoenberg [ 21 ] . Let G_{\ell}^{\lambda} denote the Gegenbauer polynomial of degree \ell . These polynomials can be defined in terms of their generating function [ 23 ] : \frac{1}{(1-2tx+x^{2})^{\lambda}}=\sum_{\ell=0}^{\infty}G_{\ell}^{\lambda}(t)x^{\ell} Schoenberg proved the following strong characterization: f(t) is a real continuous function such that the matrix f(\langle u_{i},u_{j}\rangle)_{i,j=1}^{n} is positive semidefinite for all subsets \{u_{1},\ldots,u_{n}\}\subseteq S^{r-1} if and only if f is of the form \sum_{\ell=0}^{\infty}a_{\ell}G_{\ell}^{r/2-1} with a_{\ell}\geq 0 . In particular, G_{2}^{r/2-1} and G_{4}^{r/2-1} are positive semidefinite on S^{r-1} , and we are simply using f_{2}^{r}=\frac{r-1}{r}G_{2}^{r/2-1} and f_{4}^{r}=\frac{(r-1)(r+1)}{(r+2)(r+4)}G_{4}^{r/2-1}+\frac{6}{r+4}f_{2}^{r} . Since f_{r}^{4} and f_{r}^{4} are just positive linear combinations of Gegenbauer polynomials with \lambda=r/2-1 , they