JournalsjemsVol. 22, No. 11pp. 3441–3466

Random walks on Ramanujan complexes and digraphs

  • Eyal Lubetzky

    New York University, USA
  • Alexander Lubotzky

    The Hebrew University of Jerusalem, Israel
  • Ori Parzanchevski

    The Hebrew University of Jerusalem, Israel
Random walks on Ramanujan complexes and digraphs cover
Download PDF

A subscription is required to access this article.

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 GG over a local field FF. We show that if TT is any kk-regular GG-equivariant operator on the Bruhat–Tits building with a simple combinatorial property (collision-free), the associated random walk on the nn-vertex Ramanujan complex has cutoff at time logkn_k n. The high-dimensional case, unlike that of graphs, requires tools from non-commutative harmonic analysis and the infinite-dimensional representation theory of GG. Via these, we show that operators T as above on Ramanujan complexes give rise to Ramanujan digraphs with a special property (rr-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 A~n\widetilde A_n and C~2\widetilde C_2.

Cite this article

Eyal Lubetzky, Alexander Lubotzky, Ori Parzanchevski, Random walks on Ramanujan complexes and digraphs. J. Eur. Math. Soc. 22 (2020), no. 11, pp. 3441–3466

DOI 10.4171/JEMS/990