ﻻ يوجد ملخص باللغة العربية
The total-variation cutoff phenomenon has been conjectured to hold for simple random walk on all transitive expanders. However, very little is actually known regarding this conjecture, and cutoff on sparse graphs in general. In this paper we establish total-variation cutoff for simple random walk on Ramanujan complexes of type $tilde{A}_{d}$ ($dgeq1$). As a result, we obtain explicit generators for the finite classical groups $PGL_{n}(mathbb{F}_{q})$ for which the associated Cayley graphs exhibit total-variation cutoff.
In a seminal series of papers from the 80s, Lubotzky, Phillips and Sarnak applied the Ramanujan-Petersson Conjecture for $GL_{2}$ (Delignes theorem), to a special family of arithmetic lattices, which act simply-transitively on the Bruhat-Tits trees a
Ramanujan graphs are graphs whose spectrum is bounded optimally. Such graphs have found numerous applications in combinatorics and computer science. In recent years, a high dimensional theory has emerged. In this paper these developments are surveyed
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 $
We prove a conjecture raised by the work of Diaconis and Shahshahani (1981) about the mixing time of random walks on the permutation group induced by a given conjugacy class. To do this we exploit a connection with coalescence and fragmentation proce
In previous work, we have defined---intrinsically, entirely within the digital setting---a fundamental group for digital images. Here, we show that this group is isomorphic to the edge group of the clique complex of the digital image considered as a