Periodic Walks on Large Regular Graphs and Random Matrix Theory

DOI10.1080/10586458.2014.950874MaRDI QIDQ5498937zbMATH OpenOpenAlexFDO

Authors Idan Oren, Uzy Smilansky

Publication date 11 February 2015

Published in Experimental Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

adjacency eigenvaluesperiodic walksregular graphsspectral statistics

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Relations with random matrices (11M50) Random matrices (probabilistic aspects) (60B20)

Abstract: We study the distribution of the number of (non-backtracking) 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 $infty$ with $t/Vightarrowau$ for any $au$. This formula is based on the conjecture that the spectral statistics of the adjacency eigenvalues is given by Random Matrix Theory (RMT). We provide numerical and theoretical evidence for the validity of this conjecture. The key tool used in this study is a trace formula which expresses the spectral density of $d$-regular graphs, in terms of periodic walks.

Recommendations

• Random walks on periodic graphs
• Random Walks on Regular and Irregular Graphs
• scientific article; zbMATH DE number 2046058
• scientific article; zbMATH DE number 2128200
• Adjacency and transition matrices related to random walks on graphs
• Loop-erased walks and random matrices
• Random walks on graphs: ideas, techniques and results
• scientific article; zbMATH DE number 4197088
• Random walks on dense graphs and graphons

Cites work

• A proof of Alon’s second eigenvalue conjecture and related problems
• Automorphic forms and geometry of arithmetic varieties
• Discrete path integral approach to the Selberg trace formula for regular graphs
• Expander graphs and their applications
• On orthogonal and symplectic matrix ensembles
• Random matrix theory and (1/2+it).
• Semiclassical theory of spectral rigidity
• The expected eigenvalue distribution of a large regular graph
• THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
• Trace formulae and spectral statistics for discrete laplacians on regular graphs. I
• Trace formulas and spectral statistics for discrete Laplacians on regular graphs (II)

Cited in

(4)

• Random walks on periodic graphs
• Trace formulas and spectral statistics for discrete Laplacians on regular graphs (II)
• Trace formulae and spectral statistics for discrete laplacians on regular graphs. I
• Periodicity for the Hadamard Walk on Cycles

This page was built for publication: Periodic Walks on Large Regular Graphs and Random Matrix Theory

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