Cutoff on all Ramanujan graphs

DOI10.1007/s00039-016-0382-7zbMath1351.05208arXiv1507.04725OpenAlexW2964343896MaRDI QIDQ343522

Eyal Lubetzky, Yuval Peres

Publication date: 28 November 2016

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

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

zbMATH Keywords

simple random walk\(d\)-regular Ramanujan graphs

Mathematics Subject Classification ID

Random walks on graphs (05C81)

Related Items

Universality of cutoff for graphs with an added random matching, Cutoff for random lifts of weighted graphs, Quantum ergodicity on regular graphs, An entropic proof of cutoff on Ramanujan graphs, Cutoff on graphs and the Sarnak-Xue density of eigenvalues, Cutoff on Ramanujan complexes and classical groups, Random walk on sparse random digraphs, CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS, A note on the trace method for random regular graphs, Geometry of random Cayley graphs of abelian groups, Cutoff profile of the metropolis biased card shuffling, Cutoff for permuted Markov chains, On Sarnak’s Density Conjecture and Its Applications, Nilprogressions and groups with moderate growth, Simple versus nonsimple loops on random regular graphs, Super-Golden-Gates for \(PU(2)\), Speeding up Markov chains with deterministic jumps, Random walks on Ramanujan complexes and digraphs, Cutoff at the ``entropic time for sparse Markov chains, Ramanujan Graphs in Cryptography, Frogs on trees?, Some spectral properties of the non-backtracking matrix of a graph, \(L^p\)-expander graphs, Reversibility of the non-backtracking random walk, The spectral gap of sparse random digraphs, Recent results of quantum ergodicity on graphs and further investigation, A combinatorial proof of Bass's determinant formula for the zeta function of regular graphs, Correction to: ``Speeding up Markov chains with deterministic jumps, Limit profiles for reversible Markov chains, On the local geometry of graphs in terms of their spectra, From Ramanujan graphs to Ramanujan complexes, Cutoff on hyperbolic surfaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Explicit expanders with cutoff phenomena
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Denumerable Markov chains. Generating functions, boundary theory, random walks on trees.
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Cutoff phenomena for random walks on random regular graphs
• Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski
• The cutoff phenomenon for ergodic Markov processes
• Ramanujan graphs
• Eigenvalues and expanders
• On the second eigenvalue of a graph
• Finite range random walk on free groups and homogeneous trees
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Probability on Trees and Networks
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Expander graphs and their applications
• A proof of Alon’s second eigenvalue conjecture and related problems
• Shuffling Cards and Stopping Times
• Diameters and Eigenvalues
• Generating a random permutation with random transpositions
• An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian
• THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
• The non-backtracking spectrum of the universal cover of a graph
• Répartition asymptotique des valeurs propres de l’opérateur de Hecke 𝑇_𝑝