The non-backtracking spectrum of the universal cover of a graph
Dr. Shlomo Hoory
University of British Columbia

Abstract:

A non-backtracking walk on a graph, H, is a directed path of directed  edges of H such that no edge is the inverse of its preceding edge.  Non-backtracking walks of a given length can be counted using the  non-backtracking matrix, B, indexed by H's directed edges and related  to Ihara's Zeta function.

 I will show how to determine B's spectrum in the case where H is a tree  covering a finite graph. When H is not regular, this spectrum can have  positive measure in the complex plane, unlike the regular case. Also,  I will show that outside of B's spectrum, the corresponding  Green function has ``periodic decay ratios,'' and that the existence  of such a ``ratio system'' can be effectively checked, and is equivalent  to being outside the spectrum.

 I will give experimental evidence that for a fixed, finite graph, H, a  random lift of large degree has non-backtracking new spectrum near that  of H's universal cover. This is a generalization of Alon's second  eigenvalue conjecture.

Joint work with Omer Angel and Joel Friedman.