2025/09/08 by Guo, Yuhan, Zhang, Dong
#Combinatorics (math.CO) #FOS: Mathematics #Spectral Theory (math.SP)
paper · doi:10.48550/arxiv.2509.06247
We show that for any connected graph G with maximum degree d≥3, the spectral gap from 0 with respect to the adjacency matrix is at most √(d-1), with equality if and only if G is the incidence graph of a finite projective plane of order d-1; and for other cases, the bound √(d-1) is improved to √(d-2). This is a spectral gap version of a result by Mohar and Tayfeh-Rezaie. Moreover, for d-regular graphs with girth at least 7, the bound √(d-2) is further improved to √(d-c(d)) where c(d)≥ 2 and limd→∞c(d)/d=(√(5)-1)/2. A similar yet more subtle phenomenon involving the normalized Laplacian is also investigated, where we work on graphs of degrees ≥ d rather than ≤ d. We prove that for any graph G with minimum degree d≥ 3, the spectral gap from the value 1 with respect to the normalized Laplacian is at most √(d-1)/d, with equality if and only if G is the incidence graph of a finite projective plane of order d-1. As an application, we provide a new sharp bound for the convergence rate of some eigenvalues of the Laplacian on the weighted neighborhood graphs introduced by Bauer and Jost.