Periodic Walks on Large Regular Graphs and Random Matrix Theory

Abstract

We study the distribution of the number of (nonbacktracking) periodic walks on large regular graphs. We propose a formula for the ratio between the variance of the number of t-periodic walks and its mean when the cardinality of the vertex set V and the period t approach ∞ as t/V → τ for all τ. This formula is based on the conjecture that the spectral statistics of the adjacency eigenvalues are given by random matrix theory. We provide numerical and theoretical evidence for the validity of this conjecture. The key tool used in this study is a trace formula that expresses the spectral density of d-regular graphs in terms of periodic walks.

2000 AMS Subject Classification::

• 11M50
• 05C80

Keywords:

• d-regular graphs
• spectral statistics
• cycle counting