Cutoff on all Ramanujan graphs

DOI10.1007/S00039-016-0382-7MaRDI QIDQ343522zbMATHOpenAlexFDO

Authors 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

\(d\)-regular Ramanujan graphssimple random walk

Mathematics Subject Classification ID

Random walks on graphs (05C81)

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$.

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

Cites work

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

Cited in

(43)

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

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)