Support of closed walks and second eigenvalue multiplicity of graphs
Authors:
Open Access
- 15 June 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 396-407
Abstract
We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree Δ is bounded by O(n Δ7/5/log1/5−o(1)n) for any Δ, and improve this to O(nlog1/2d/log1/4−o(1)n) for simple d-regular graphs when d≥ log1/4n. In fact, the same bounds hold for the number of eigenvalues in any interval of width λ2/logΔ1−o(1)n containing the second eigenvalue λ2. The main ingredient in the proof is a polynomial (in k) lower bound on the typical support of a closed random walk of length 2k 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.Keywords
All Related Versions
Funding Information
- National Science Foundation (CCF-155375, CCF-200901, DGE-175281)
- Villum Fonden (16582)
This publication has 13 references indexed in Scilit:
- Subexponential Algorithms for Unique Games and Related ProblemsJournal of the ACM, 2015
- Making the Long Code ShorterSIAM Journal on Computing, 2015
- Multiway Spectral Partitioning and Higher-Order Cheeger InequalitiesJournal of the ACM, 2014
- Many sparse cuts via higher eigenvalues2012
- A Chernoff Bound for Random Walks on Expander GraphsSIAM Journal on Computing, 1998
- Large Deviation Bounds for Markov ChainsCombinatorics, Probability and Computing, 1997
- Eigenvalues and expansion of regular graphsJournal of the ACM, 1995
- More on Graph PerturbationsBulletin of the London Mathematical Society, 1990
- Ramanujan graphsCombinatorica, 1988
- The expected eigenvalue distribution of a large regular graphLinear Algebra and its Applications, 1981