The non-backtracking spectrum of the universal cover of a graph

DOI10.1090/S0002-9947-2014-06255-7zbMath1310.05136arXiv0712.0192OpenAlexW2023708440MaRDI QIDQ5247000

Joel Friedman, Shlomo Hoory, Omer Angel

Publication date: 22 April 2015

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

ratio systemnon-backtracking walks

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (33)

The Bethe Hessian and information theoretic approaches for online change-point detection in network data ⋮ Spectral gap in random bipartite biregular graphs and applications ⋮ Ihara Zeta Functions of Infinite Weighted Graphs ⋮ Cutoff on all Ramanujan graphs ⋮ Cooperative epidemics spreading under resource control ⋮ On the exponential generating function for non-backtracking walks ⋮ On weighted spectral radius of unraveled balls and normalized Laplacian eigenvalues ⋮ A new weighted Ihara zeta function for a graph ⋮ Detection thresholds in very sparse matrix completion ⋮ Spectra of infinite graphs via freeness with amalgamation ⋮ Spectral theory of the non-backtracking Laplacian for graphs ⋮ Correlation Bounds for Distant Parts of Factor of IID Processes ⋮ Expander graphs and their applications ⋮ Simple versus nonsimple loops on random regular graphs ⋮ On the stability of multilayer Boolean networks under targeted immunization ⋮ Expansion of random graphs: new proofs, new results ⋮ Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs ⋮ Beyond non-backtracking: non-cycling network centrality measures ⋮ Unnamed Item ⋮ Estimating the number of communities by spectral methods ⋮ Cutoff phenomena for random walks on random regular graphs ⋮ \(L^p\)-expander graphs ⋮ Algebraic bounds for heterogeneous site percolation on directed and undirected graphs ⋮ Suppressing epidemic spreading by optimizing the allocation of resources between prevention and treatment ⋮ Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph ⋮ Two accelerated non-backtracking PageRank algorithms for large-scale networks ⋮ Graphs with prescribed local neighborhoods of their universal coverings ⋮ Non-Backtracking Alternating Walks ⋮ Non-backtracking PageRank ⋮ A Theory for Backtrack-Downweighted Walks ⋮ Explicit Near-Ramanujan Graphs of Every Degree ⋮ Fragmenting complex network based on non-backtracking matrix ⋮ Eigenvalues of the non-backtracking operator detached from the bulk

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Absolutely continuous spectrum for random operators on trees of finite cone type
• A lower bound on the spectral radius of the universal cover of a graph
• Zeta functions of finite graphs and coverings. III
• Algebraic equations for Green kernel on a tree
• Spectral structure of the Laplacian on a covering graph
• Cogrowth of groups and simple random walks
• A formula of eigenfunction expansions. I: Case of asymptotic trees
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• Some geometric aspects of graphs and their eigenfunctions
• The Moore bound for irregular graphs
• Relative expanders or weakly relatively Ramanujan graphs.
• Counting paths in graphs
• Wave equations for graphs and the edge-based Laplacian
• Point spectrum on a quasi homogeneous tree
• On the spectral theory of trees with finite cone type
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Modern Coding Theory
• Expander graphs and their applications
• A proof of Alon’s second eigenvalue conjecture and related problems
• Non-Backtracking Random Walks and Cogrowth of Graphs
• Cogrowth of Regular Graphs
• Harmonic analysis for anisotropic random walks on homogeneous trees
• THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE

This page was built for publication: The non-backtracking spectrum of the universal cover of a graph