Support of closed walks and second eigenvalue multiplicity of graphs

DOI10.1145/3406325.3451129MaRDI QIDQ6087011zbMATH OpenOpenAlexFDO

Authors Theo McKenzie, Peter M. R. Rasmussen, Nikhil Srivastava

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.12819

zbMATH Keywords

eigenvalue multiplicitynormalized adjacency matrixrandom walks in graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree $Delta$ is bounded by $O(nDelt{a}^{7/5}/lo{g}^{1/5-o(1)}n)$ for any $Delta$, and by $O(nlo{g}^{1/2}d/lo{g}^{1/4-o(1)}n)$ for simple $d$-regular graphs when $dgelo{g}^{1/4}n$. In fact, the same bounds hold for the number of eigenvalues in any interval of width $lambd{a}_2/lo{g}_{D}elt{a}^{1-o(1)}n$ containing the second eigenvalue $lambd{a}_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.

Recommendations

• Closed walks and eigenvalues of abelian Cayley graphs
• On the second eigenvalue and random walks in random d-regular graphs
• The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs
• Multiplicity of  the second‐largest eigenvalue of a planar graph
• Walks and eigenvalues of signed graphs
• Bounds on the number of closed walks in a graph and its applications
• The second largest eigenvalue and vertex-connectivity of regular multigraphs
• On the second eigenvalue of hypergraphs
• Graphs with high second eigenvalue multiplicity
• Walks and the spectral radius of graphs

Cited in

(6)

• Graphs with high second eigenvalue multiplicity
• Maximal multiplicity of Laplacian eigenvalues in negatively curved surfaces
• Equiangular lines via matrix projection
• Graph theory. Abstracts from the workshop held January 5--10, 2025
• Limit vectors of the top k eigenvalues of d-regular graphs
• Sparsest cut and eigenvalue multiplicities on low degree abelian Cayley graphs

This page was built for publication: Support of closed walks and second eigenvalue multiplicity of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087011)