Cutoff on all Ramanujan graphs

DOI10.1007/S00039-016-0382-7zbMATH Open1351.05208arXiv1507.04725OpenAlexW2964343896MaRDI QIDQ343522FDOQ343522

Authors: Eyal Lubetzky, Yuval Peres 

Publication date: 28 November 2016

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

Abstract: We show that on every Ramanujan graph $G$, the simple random walk exhibits cutoff: when $G$ has $n$ vertices and degree $d$, the total-variation distance of the walk from the uniform distribution at time $t=fracdd-2lo{g}_{d-1}n+ssqrtlogn$ is asymptotically $mathbbP(Z>c,s)$ where $Z$ is a standard normal variable and $c=c(d)$ is an explicit constant. Furthermore, for all $1leqpleqinfty$, $d$-regular Ramanujan graphs minimize the asymptotic $L^p$-mixing time for SRW among all $d$-regular graphs. Our proof also shows that, for every vertex $x$ in $G$ as above, its distance from $n-o(n)$ of the vertices is asymptotically $lo{g}_{d-1}n$.

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

Recommendations

• Cutoff for Ramanujan graphs via degree inflation
• An entropic proof of cutoff on Ramanujan graphs
• Random walks on Ramanujan complexes and digraphs
• Cutoff phenomena for random walks on random regular graphs
• Cutoff on Ramanujan complexes and classical groups

zbMATH Keywords

\(d\)-regular Ramanujan graphssimple random walk

Mathematics Subject Classification ID

Random walks on graphs (05C81)

Cites Work

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

Cited In (42)

• On the local geometry of graphs in terms of their spectra
• The spectral gap of sparse random digraphs
• An entropic proof of cutoff on Ramanujan graphs
• From Ramanujan graphs to Ramanujan complexes
• Geometry of random Cayley graphs of abelian groups
• Cutoff profile of the metropolis biased card shuffling
• Cutoff for random lifts of weighted graphs
• Cutoff for permuted Markov chains
• Correction to: ``Speeding up Markov chains with deterministic jumps
• The varentropy criterion is sharp on expanders
• Super-Golden-Gates for \(PU(2)\)
• Cutoff at the ``entropic time for sparse Markov chains
• Frogs on trees?
• Some spectral properties of the non-backtracking matrix of a graph
• Cut-off for large sums of graphs
• Random walk on sparse random digraphs
• Ramanujan Graphs in Cryptography
• \(L^p\)-expander graphs
• Cutoff for Ramanujan graphs via degree inflation
• Orientations and cycles in supersingular isogeny graphs
• A note on the trace method for random regular graphs
• On Sarnak’s Density Conjecture and Its Applications
• Simple versus nonsimple loops on random regular graphs
• Recent results of quantum ergodicity on graphs and further investigation
• Quantum ergodicity on regular graphs
• Cutoff on Ramanujan complexes and classical groups
• Nilprogressions and groups with moderate growth
• Isogeny graphs on superspecial abelian varieties: eigenvalues and connection to Bruhat-Tits buildings
• Reversibility of the non-backtracking random walk
• CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS
• Limit profiles for projections of random walks on groups
• A combinatorial proof of Bass's determinant formula for the zeta function of regular graphs
• Spectral correspondences for finite graphs without dead ends
• Limit profiles for reversible Markov chains
• Cutoff on hyperbolic surfaces
• Cutoff phenomena for random walks on random regular graphs
• Speeding up Markov chains with deterministic jumps
• Universality of cutoff for graphs with an added random matching
• Cutoff for non-negatively curved Markov chains
• Cutoff on graphs and the Sarnak-Xue density of eigenvalues
• Comparing limit profiles of reversible Markov chains
• Random walks on Ramanujan complexes and digraphs

This page was built for publication: Cutoff on all Ramanujan graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q343522)