Support of closed walks and second eigenvalue multiplicity of graphs

We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree Δ is bounded by 𝑂 (𝑛Δ 7/5 /log 1/5-𝑜 (1) 𝑛) for any Δ, and improve this to 𝑂 (𝑛 log 1/2 𝑑/log 1/4-𝑜 (1) 𝑛) for simple 𝑑-regular graphs when 𝑑 ≥ log 1/4 𝑛. In fact, the same bounds hold for the number of eigenvalues in any interval of width 𝜆 2 /log 1-𝑜 (1) Δ 𝑛 containing the second eigenvalue 𝜆 2 . The main ingredient in the proof is a polynomial (in 𝑘) lower bound on the typical support of a closed random walk of length 2𝑘 in any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix.

• Mathematics of computing → Spectra of graphs; • Theory of computation → Random walks and Markov chains.