Random walks on Ramanujan complexes and digraphs

DOI10.4171/JEMS/990zbMATH Open1454.05114arXiv1702.05452OpenAlexW3104652701MaRDI QIDQ2216740FDOQ2216740

Authors: Eyal Lubetzky, Ori Parzanchevski, Alexander Lubotzky 

Publication date: 17 December 2020

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Abstract: The cutoff phenomenon was recently confirmed for random walks on Ramanujan graphs by the first author and Peres. In this work, we obtain analogs in higher dimensions, for random walk operators on any Ramanujan complex associated with a simple group $G$ over a local field $F$. We show that if $T$ is any $k$-regular $G$-equivariant operator on the Bruhat-Tits building with a simple combinatorial property (collision-free), the associated random walk on the $n$-vertex Ramanujan complex has cutoff at time $lo{g}_{k}n$. The high dimensional case, unlike that of graphs, requires tools from non-commutative harmonic analysis and the infinite-dimensional representation theory of $G$. Via these, we show that operators $T$ as above on Ramanujan complexes give rise to Ramanujan digraphs with a special property ($r$-normal), implying cutoff. Applications include geodesic flow operators, geometric implications, and a confirmation of the Riemann Hypothesis for the associated zeta functions over every group $G$, previously known for groups of type $widetilde{A}_n$ and $widetilde{C}_2$.

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

Recommendations

• Cutoff on Ramanujan complexes and classical groups
• Cutoff on all Ramanujan graphs
• An entropic proof of cutoff on Ramanujan graphs
• Cutoff for Ramanujan graphs via degree inflation
• From Ramanujan graphs to Ramanujan complexes

zbMATH Keywords

cutoff phenomenonRamanujan complexeshigh dimensional expandersmixing time of random walk

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Directed graphs (digraphs), tournaments (05C20) Combinatorial aspects of representation theory (05E10) Random walks on graphs (05C81) Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Shuffling Cards and Stopping Times
• Generating a random permutation with random transpositions
• Title not available (Why is that?)
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• On discrete subgroups of the two by two projective linear group over \(p\)-adic fields
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ramanujan graphs
• Drinfeld shtukas and Langlands correspondence.
• Title not available (Why is that?)
• The cutoff phenomenon in finite Markov chains.
• Zeta functions of complexes arising from \(\mathrm{PGL}(3)\)
• Overlap properties of geometric expanders
• Mixing properties and the chromatic number of Ramanujan complexes
• Title not available (Why is that?)
• The Zeta Functions of Complexes from Sp(4)
• Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).
• The zeta functions of complexes from \(\mathrm{PGL}(3)\): a representation-theoretic approach
• Ramanujan complexes of type \(\widetilde A_d\)
• Title not available (Why is that?)
• Cutoff on all Ramanujan graphs
• Cutoff phenomena for random walks on random regular graphs
• Title not available (Why is that?)
• Ramanujan hypergraphs
• Finite quotients of Bruhat-Tits buildings as geometric expanders
• THE IHARA–SELBERG ZETA FUNCTION FOR PGL₃ AND HECKE OPERATORS
• Title not available (Why is that?)
• Riemann hypothesis and strongly Ramanujan complexes from \(\mathrm{GL}_{n}\)
• Zeta and \(L\)-functions of finite quotients of apartments and buildings

Cited In (10)

• Ramanujan complexes and golden gates in \(PU(3)\)
• From Ramanujan graphs to Ramanujan complexes
• Expander graphs -- both local and global
• Super-Golden-Gates for \(PU(2)\)
• On Sarnak’s Density Conjecture and Its Applications
• Cutoff on Ramanujan complexes and classical groups
• Cutoff on all Ramanujan graphs
• Cutoff on hyperbolic surfaces
• On a Conjecture of Bollobás and Brightwell Concerning Random Walks on Product Graphs
• Cutoff on graphs and the Sarnak-Xue density of eigenvalues

This page was built for publication: Random walks on Ramanujan complexes and digraphs

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