Cutoff on graphs and the Sarnak-Xue density of eigenvalues

DOI10.1016/J.EJC.2022.103530MaRDI QIDQ2143397zbMATH OpenOpenAlexFDO

Authors Konstantin Golubev, Amitay Kamber

Publication date 31 May 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

optimal spectrumRamanujan graphsSarnak-Xue density property

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: It was recently shown by Lubetzky and Peres (2016) and by Sardari (2018) that Ramanujan graphs, i.e., graphs with the optimal spectrum, exhibit cutoff of the simple random walk in an optimal time and have an optimal almost-diameter. We show that this spectral condition can be replaced by a weaker condition, the Sarnak-Xue density property, to deduce similar results. This allows us to prove that some natural families of Schreier graphs of the $S{L}_2(mathbb{F}_t)$-action on the projective line exhibit cutoff, thus proving a special case of a conjecture of Rivin and Sardari.

Recommendations

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

Cites work

• \(L^p\)-expander graphs
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• A proof of alon's second eigenvalue conjecture
• An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian
• Best possible rates of distribution of dense lattice orbits in homogeneous spaces
• Bounds for multiplicities of automorphic representations
• Cutoff on all Ramanujan graphs
• Diameter of Ramanujan graphs and random Cayley graphs
• Expander graphs and their applications
• scientific article; zbMATH DE number 3968677 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 1849959 (Why is no real title available?)
• Kesten's theorem for invariant random subgroups.
• Line graphs, root systems, and elliptic geometry
• On the girth of random Cayley graphs
• On the spectral gap for infinite index ``congruence subgroups of \(SL_2(\mathbb{Z})\)
• Quantum chaos on random Cayley graphs of \(\mathrm{SL}_2 [\mathbb{Z}/ p\mathbb{Z}]\)
• Quasirandom Groups
• Ramanujan coverings of graphs
• Ramanujan graphs
• Random walks on Ramanujan complexes and digraphs
• Super-Golden-Gates for PU(2)
• The measurable Kesten theorem
• Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).

Cited in

(8)

• Mixing time of fractional random walk on finite fields
• \(L^p\)-expander graphs
• Cutoff on hyperbolic surfaces
• Location of the eigenvalues of weighted graphs with a cut edge
• On Sarnak’s Density Conjecture and Its Applications
• The density hypothesis for horizontal families of lattices
• Small diameters and generators for arithmetic lattices in \(\mathrm{SL}_2 (\mathbb{R})\) and certain Ramanujan graphs
• Cutoff for geodesic paths on hyperbolic manifolds

This page was built for publication: Cutoff on graphs and the Sarnak-Xue density of eigenvalues

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