Support of closed walks and second eigenvalue multiplicity of graphs
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Support of closed walks and second eigenvalue multiplicity of graphs. / McKenzie, Theo; Rasmussen, Peter Michael Reichstein; Srivastava, Nikhil.
STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. ed. / Samir Khuller; Virginia Vassilevska Williams. Association for Computing Machinery, Inc., 2021. p. 396-407.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Support of closed walks and second eigenvalue multiplicity of graphs
AU - McKenzie, Theo
AU - Rasmussen, Peter Michael Reichstein
AU - Srivastava, Nikhil
N1 - Publisher Copyright: © 2021 Owner/Author.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - eigenvalue multiplicity
KW - normalized adjacency matrix
KW - random walks in graphs
U2 - 10.1145/3406325.3451129
DO - 10.1145/3406325.3451129
M3 - Article in proceedings
AN - SCOPUS:85108158158
SP - 396
EP - 407
BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
A2 - Khuller, Samir
A2 - Williams, Virginia Vassilevska
PB - Association for Computing Machinery, Inc.
T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Y2 - 21 June 2021 through 25 June 2021
ER -
ID: 306692967