Graph Eigenvalues and Projection Constants

2026/08/03 by Varun Sivashankar, Quanyu Tang, Tanay Wakhare
Mathematics · #math.CO #msc:05C50 #msc:15A18 #msc:15A42

paper · pdf

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

arxiv created 2026/08/03 · arxiv updated 2026/08/04

Abstract

For an integer k≥2, let λ_k(G) denote the kth largest adjacency eigenvalue of a graph G. For every graph G on n vertices and every 2 ≤ k ≤ n, we prove λ_k(G) ≤ ((k-2)√(k+1)+2)/(2k(k-1)) n-1. Our bound is tight for k∈\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 γ(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≥4 for which r+2 is not a perfect square.

Citations

• Generalized Nordhaus--Gaddum Inequalities for Eigenvalues
• Spaces with the maximal projection constant revisited
• Strengthened upper bound on the third eigenvalue of graphs
• On graphs with large third eigenvalue
• Improved lower bounds on the extrema of eigenvalues of graphs
• Equiangular lines, Incoherent sets and Quasi-symmetric designs
• Nearly orthogonal vectors and small antipodal spherical codes
• Extrema of graph eigenvalues
• Bounds on graph eigenvalues I
• The Difference Between Consecutive Primes, II
• Norms of Minimal Projections