Eigenvalues of Non-Backtracking Walks in a Cycle with Random Loops

Authors

Ana Pop, University of British ColumbiaFollow

Abstract

In this paper we take a very special model of a random non-regular graph and study its non-backtracking spectrum. We study graphs consisting of a cycle with some random loops added; the graphs are not regular and their non-backtracking spectrum does not seem to be confined to some one-dimensional set in the complex plane. The non-backtracking spectrum is required in some applications, and has no straightforward connection to the usual adjacency matrix spectrum for general graphs, unlike the situation for regular graphs. Experimentally, the random graphs' spectrum appears similar in shape to its deterministic counterpart, but differs because the eigenvalues are visibly clustered, especially with a mysterious gap around Re(l)=1.

Author Bio

Ana Pop completed a BASc. in Computer Engineering with Honours Mathematics at the University of British Columbia (UBC) in 2007. She has worked over the past three summers under NSERC Undergraduate Student Research Awards (USRA) in the UBC Mathematics and Computer Science Departments. This paper was the result of work done under her second USRA. Her main interests lie in the field of bioinformatics, and is starting a PhD program in Computer Science at Princeton University.

Faculty Sponsor

Joel Friedman

Recommended Citation

Pop, Ana (2007) "Eigenvalues of Non-Backtracking Walks in a Cycle with Random Loops," Rose-Hulman Undergraduate Mathematics Journal: Vol. 8: Iss. 2, Article 10.
Available at: https://scholar.rose-hulman.edu/rhumj/vol8/iss2/10