Support of closed walks and second eigenvalue multiplicity of graphs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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.

Original languageEnglish
Title of host publicationSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
EditorsSamir Khuller, Virginia Vassilevska Williams
PublisherAssociation for Computing Machinery, Inc.
Publication date2021
ISBN (Electronic)9781450380539
Publication statusPublished - 2021
Event53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy
Duration: 21 Jun 202125 Jun 2021


Conference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
ByVirtual, Online
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT)

Bibliographical note

Publisher Copyright:
© 2021 Owner/Author.

    Research areas

  • eigenvalue multiplicity, normalized adjacency matrix, random walks in graphs

ID: 306692967