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

McKenzie, T, Rasmussen, PMR & Srivastava, N 2021, Support of closed walks and second eigenvalue multiplicity of graphs. in S Khuller & VV Williams (eds), STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, Inc., pp. 396-407, 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, Virtual, Online, Italy, 21/06/2021. https://doi.org/10.1145/3406325.3451129

APA

McKenzie, T., Rasmussen, P. M. R., & Srivastava, N. (2021). Support of closed walks and second eigenvalue multiplicity of graphs. In S. Khuller, & V. V. Williams (Eds.), STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (pp. 396-407). Association for Computing Machinery, Inc.. https://doi.org/10.1145/3406325.3451129

Vancouver

McKenzie T, Rasmussen PMR, Srivastava N. Support of closed walks and second eigenvalue multiplicity of graphs. In Khuller S, Williams VV, editors, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, Inc. 2021. p. 396-407 https://doi.org/10.1145/3406325.3451129

Author

McKenzie, Theo ; Rasmussen, Peter Michael Reichstein ; Srivastava, Nikhil. / Support of closed walks and second eigenvalue multiplicity of graphs. STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. editor / Samir Khuller ; Virginia Vassilevska Williams. Association for Computing Machinery, Inc., 2021. pp. 396-407

Bibtex

@inproceedings{46312888e6274bcdaf6b27c8d4edfabc,
title = "Support of closed walks and second eigenvalue multiplicity of graphs",
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 = "eigenvalue multiplicity, normalized adjacency matrix, random walks in graphs",
author = "Theo McKenzie and Rasmussen, {Peter Michael Reichstein} and Nikhil Srivastava",
note = "Publisher Copyright: {\textcopyright} 2021 Owner/Author.; 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 ; Conference date: 21-06-2021 Through 25-06-2021",
year = "2021",
doi = "10.1145/3406325.3451129",
language = "English",
pages = "396--407",
editor = "Samir Khuller and Williams, {Virginia Vassilevska}",
booktitle = "STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing",
publisher = "Association for Computing Machinery, Inc.",

}

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