Random walks on Ramanujan complexes and digraphs

E. Lubetzky, A. Lubotzky, O. Parzanchevski

Research output: Contribution to journalArticlepeer-review

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 logk 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 Aen and Ce2

Original languageEnglish (US)
Pages (from-to)3441-3466
Number of pages26
JournalJournal of the European Mathematical Society
Volume22
Issue number11
DOIs
StatePublished - 2020

Keywords

  • Cutoff phenomenon
  • High dimensional expanders
  • Mixing time of random walk
  • Ramanujan complexes

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Random walks on Ramanujan complexes and digraphs'. Together they form a unique fingerprint.

Cite this