Support of closed walks and second eigenvalue multiplicity of graphs

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

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.

OriginalsprogEngelsk
TitelSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
RedaktørerSamir Khuller, Virginia Vassilevska Williams
ForlagAssociation for Computing Machinery, Inc.
Publikationsdato2021
Sider396-407
ISBN (Elektronisk)9781450380539
DOI
StatusUdgivet - 2021
Begivenhed53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italien
Varighed: 21 jun. 202125 jun. 2021

Konference

Konference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
LandItalien
ByVirtual, Online
Periode21/06/202125/06/2021
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT)

Bibliografisk note

Funding Information:
Theo McKenzie is supported by NSF Grant DGE-1752814. Peter Rasmussen is supported by grant 16582, Basic Algorithms Research Copenhagen (BARC), from the VILLUM Foundation. Nikhil Srivas-tava is supported by NSF Grants CCF-1553751 and CCF-2009011.

Publisher Copyright:
© 2021 Owner/Author.

ID: 306692967