Eigenvalues and Spectrum of non-backtracking Matrix in Graphs
Eigenvalues and Spectrum of non-backtracking Matrix in Graphs
Mohammadesmail Nikfar1
1) Associate Professor, Ph.D. in Mathematics, Department of Mathematics, School of Hekmat 1, District 4, Tehran, Iran.
IOI Code
:
ADDG-ACAEHE
Publication :
The Second International Conference on New Developments in Educational, Training, Psychology, Skill Training and Skill-Based Systems with a Focus on Education in the Third Millennium(https://www.cseconf.ir/2nd)
Abstract :
A non-backtracking walk on a graph is a directed path consisting of directed edges of $H$, such that no edge is the reverse of the preceding one. Non-backtracking walks of any given length can be counted using the non-backtracking adjacency matrix; this matrix is indexed by the directed edges of $H$ and is related to the Ihara zeta function. The study addresses how to determine the spectrum of this operator in the case where $H$ is the universal covering tree of a finite graph. Unlike the regular case, when $H$ is not regular, this spectrum may have a positive measure in the complex plane. Outside this spectrum, the corresponding Green's function exhibits exponential decay; the existence of such a decay property can be effectively verified and is equivalent to lying outside the spectrum. We further 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 co-growth (or the growth rate) of the tree. A further motivation for this research is the graph-theoretic analogue of the Riemann Hypothesis, as proposed by Stark and Terras. Finally, for a fixed finite graph $H$, a random lift of sufficiently high degree possesses a non-backtracking spectrum that approximates the spectrum of the universal cover of $H$. This result 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 without revision transition without revision eigenvalue eigenvector