Cutoff on all Ramanujan graphs

DOI10.1007/S00039-016-0382-7MaRDI QIDQ343522zbMATH OpenOpenAlexFDO

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

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• 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
• 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?)
• 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 cutoff phenomenon for ergodic Markov processes
• THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
• The non-backtracking spectrum of the universal cover of a graph

Cited in

(54)

• Rates of convergence of random walk on distance regular graphs
• 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
• The spectral gap of sparse random digraphs
• Correction to: ``Speeding up Markov chains with deterministic jumps
• Limit profiles for reversible Markov chains
• Universality of cutoff for graphs with an added random matching
• Cutoff for random lifts of weighted graphs
• Cutoff on graphs and the Sarnak-Xue density of eigenvalues
• Cutoff on Ramanujan complexes and classical groups
• Speeding up Markov chains with deterministic jumps
• Random walks on Ramanujan complexes and digraphs
• \(L^p\)-expander graphs
• Reversibility of the non-backtracking random walk
• Recent results of quantum ergodicity on graphs and further investigation
• On the local geometry of graphs in terms of their spectra
• Cutoff on hyperbolic surfaces
• Quantum ergodicity on regular graphs
• Cutoff for Ramanujan graphs via degree inflation
• Random walk on sparse random digraphs
• Cut-off for large sums of graphs
• Cutoff for permuted Markov chains
• Ramanujan graphs in cryptography
• From Ramanujan graphs to Ramanujan complexes
• Cutoff at the entropic time for random walks on covered expander graphs
• A combinatorial proof of Ihara-Bass's formula for the zeta function of regular graphs
• A note on the trace method for random regular graphs
• Bounded cutoff window for the non-backtracking random walk on Ramanujan graphs
• Geometry of random Cayley graphs of abelian groups
• Cutoff profile of the metropolis biased card shuffling
• On Sarnak’s Density Conjecture and Its Applications
• Simple versus nonsimple loops on random regular graphs
• Comparing limit profiles of reversible Markov chains
• The varentropy criterion is sharp on expanders
• Orientations and cycles in supersingular isogeny graphs
• Cutoff for non-negatively curved Markov chains
• Isogeny graphs on superspecial abelian varieties: eigenvalues and connection to Bruhat-Tits buildings
• Limit profiles for projections of random walks on groups
• Spectral correspondences for finite graphs without dead ends
• Cutoff for contingency table and torus random walks with low incremental correlations
• Mixing trichotomy for random walks on directed stochastic block models
• Defective eigenvalues of the non-backtracking matrix
• Quantum-classical correspondences for locally symmetric spaces
• Limit profile for the transpose top-2 with random shuffle
• Edge Laplacians and edge Poisson transforms for graphs
• A pairing formula for resonant states on finite regular graphs
• Restart perturbations for reversible Markov chains: trichotomy and pre-cutoff equivalence
• Sublinear time shortest path in expander graphs
• Cutoff for geodesic paths on hyperbolic manifolds
• An entropic proof of cutoff on Ramanujan graphs
• Nilprogressions and groups with moderate growth
• Cutoff phenomena for random walks on random regular graphs

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)