Forming Eigenvalues for Walk Matrix Without Re-derivation

Forming Eigenvalues for Walk Matrix Without Re-derivation

Mohammadesmail Nikfar1

1) Ph.D. Graduate in Mathematics, Doctor of Philosophy (Ph.D.) in Pure Mathematics, Mathematics Teacher, District 4 Department of Education, Tehran, Iran

IOI Code : ACHG-ACACKH
Publication : (13gtacc.sru.ac.ir)
Abstract :
    A non-backtracking walk on a graph is a directed path consisting of directed edges, such that no edge is the reverse of the preceding one. Non-backtracking walks of any arbitrary length can be enumerated using a non-backtracking adjacency matrix; this matrix is ​​indexed by the directed edges and is related to the Ihara zeta function. We investigate the spectrum of this operator in the case where the graph is the universal covering tree of a finite graph. Unlike the regular case, when the graph is not regular, this spectrum may possess a positive measure in the complex plane. Outside of this spectrum, the corresponding Green's function exhibits alternating decay rates. The existence of such a decay structure can be effectively verified and is equivalent to lying outside the spectrum. Furthermore, we prove that the spectral radius of the non-backtracking walk operator on the universal covering tree of a finite graph is exactly equal to the square root of $g_r$, where $g_r$ represents the growth rate of the tree. A primary motivation for this research is the "Riemann hypothesis for graphs," as proposed by Stark and Terras. Finally, for a fixed finite graph, a random lift of sufficiently high degree possesses a non-backtracking spectrum that closely approximates that of the universal covering tree. This offers a new generalization of Alon's second eigenvalue theorem. In short, this review article aims to cover the relevant body of research, enabling the reader to quickly grasp the significance of the work.

Keywords : transition matrix transition eigenvalue eigenvector