Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCutoff on Ramanujan complexes and classical groups
168
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 associated with $SL_{2}(mathbb{Q}_{p})$. As a result, they obtained explicit Ramanujan Cayley graphs from $PSL_{2}left(mathbb{F}_{p}right)$, as well as optimal topological generators (Golden Gates) for the compact Lie group $PU(2)$. In higher dimension, the naive generalization of the Ramanujan Conjecture fails, due to the phenomenon of endoscopic lifts. In this paper we overcome this problem for $PU_{3}$ by constructing a family of arithmetic lattices which act simply-transitively on the Bruhat-Tits buildings associated with $SL_{3}(mathbb{Q}_{p})$ and $SU_{3}(mathbb{Q}_{p})$, while at the same time do not admit any representation which violates the Ramanujan Conjecture. This gives us Ramanujan complexes from $PSL_{3}(mathbb{F}_{p})$ and $PU_{3}left(mathbb{F}_{p}right)$, as well as golden gates for $PU(3)$.
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. After explaining their connection to the Ramanujan conjecture we will present some old and new results with an emphasis on random walks on these discrete objects and on the Euclidean spheres. The latter lead to golden gates which are of importance in quantum computation.
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 $log_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$.
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 processes and control the Kantorovitch distance by using a variant of a coupling due to Oded Schramm. Recasting our proof in the language of Ricci curvature, our proof establishes the occurrence of a phase transition, which takes the following form in the case of random transpositions: at time $cn/2$, the curvature is asymptotically zero for $cle 1$ and is strictly positive for $c>1$.
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 graph. The clique complex is a simplicial complex and its edge group is well-known to be isomorphic to the ordinary (topological) fundamental group of its geometric realization. This identification of our intrinsic digital fundamental group with a topological fundamental group---extrinsic to the digital setting---means that many familiar facts about the ordinary fundamental group may be translated into their counterparts for the digital fundamental group: The digital fundamental group of any digital circle is $mathbb{Z}$; a version of the Seifert-van Kampen Theorem holds for our digital fundamental group; every finitely presented group occurs as the (digital) fundamental group of some digital image. We also show that the (digital) fundamental group of every 2D digital image is a free group.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
