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

By Ana-Diana Pop. 2007

170 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/91d056107f83ff0b8fa45bf9e25abad7fb5aa4bb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Comparison of Metric Spectral Gaps (2013, background): “If G is a uniformly random n-vertex d-regular graph then by [15] λ(G) 6 2/ 4 √ d with high probability (for the best known bound on λ(G) when G is a random d-regular graph, see [35]).”
Size biased couplings and the spectral gap for random regular graphs (2015, methodology): “After pioneering work by Broder and Shamir [14], Kahn and Szemerédi [28] and Friedman [26], Friedman proved Alon’s conjecture in [27], showing that for any fixed d ≥ 3 and > 0, lim n→∞ P [ λ(A) ≤ 2√d − 1 + ] = 1.”
Spectral techniques applied to sparse random graphs (2005, methodology): “We will use the technique of Kahn and Szemeredi [13] with some modifications.”
The spectral gap of dense random regular graphs (2016, methodology): “In our situation, the Kahn– Szeméredi argument must be adapted to take into account absence of symmetry.”
Matrix completion from a few entries (2009, methodology): “Our basic strategy (inspired by [15]) will be the following : (1) Reduce to x, y belonging to discrete sets Tm, Tn; (2) Apply union bound to these sets, with a large deviation estimate on the random variable xT(M E - vkM)y.”
Cutoff phenomena for random walks on random regular graphs (2008, background): “Although many natural families of chains are believed to exhibit cutoff, determining that cutoff occurs proves to be an extremely challenging task even for fairly simple chains, as it often requires the full understanding of the delicate behavior of these chains around the mixing threshold.”
Pseudo-random Graphs (2005, unknown): “The spectrum of Gn,d for a fixed d was studied in [38] by Friedman, Kahn and Szemerédi.”
Jellyfish: Networking Data Centers Randomly (2011, background): “5This is related to the fact that RRGs are expander graphs [11].”
Sparse regular random graphs: Spectral density and eigenvectors (2009, background): “[15] Broder, A. and Shamir, E. (1987) On the second eigenvalue of random regular graphs.”
Spectral redemption in clustering sparse networks (2013, unknown): “[22]).”
Spectral Gaps of Random Graphs and Applications (2012, methodology): “The alternative method of Kahn and Szemerédi [22], first developed for bounding the spectral gap of d-regular graphs, has been adapted quite successfully for estimating the spectral gap in the p = (log n/n) regime by Feige and Ofek [18].”
A new proof of Friedman's second eigenvalue theorem and its extension to random lifts (2015, background): “if P(Ωc ) = o(1). 2 2 Proof of Theorem 1 2.1 Overview of the proof Let us describe the strategy of proof of Theorem 1 and its main diﬃculties. Following Fu¨redi and Komlo´s [15] and Broder and Shamir [8], a natural strategy is to estimate the trace of a high power of the adjacency matrix. Namely, if”
THE NON-BACKTRACKING SPECTRUM OF THE UNIVERSAL COVER OF A GRAPH (2007, methodology): “Non-backtracking walks seem to be an essential part of various aspects of graph theory, including the Broder-Shamir trace method ([9,11, 12,14]), Ihara zeta functions of graphs ([19,26,32]), Bollobas’ question concerning girth and average degree ([2,21]), and decoding of low density linear codes…”