Ramanujan Bigraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915918114717696 |
|---|---|
| author | Evra, Shai Feigon, Brooke Maurischat, Kathrin Parzanchevski, Ori |
| author_facet | Evra, Shai Feigon, Brooke Maurischat, Kathrin Parzanchevski, Ori |
| contents | In their seminal paper, Lubotzky, Phillips and Sarnak (LPS) defined the notion of regular Ramanujan graphs and gave an explicit construction of infinite families of $(p+1)$-regular Ramanujan Cayley graphs, for infinitely many primes $p$. In this paper we extend the work of LPS and its successors to bigraphs (biregular bipartite graphs), in several aspects: we investigate the combinatorial properties of various generalizations of the notion of Ramanujan graphs, define a notion of Cayley bigraphs, and give explicit constructions of infinite families of $(p^3+1,p+1)$-regular Ramanujan Cayley bigraphs, for infinitely many $p$.
Both the LPS graphs and our ones are arithmetic, arising as quotients of Bruhat-Tits trees by congruence subgroups of arithmetic lattices in a $p$-adic group, $PGL_2(\mathbb{Q}_p)$ for LPS and $PU_3(\mathbb{Q}_p)$ for us. In both cases the Ramanujan property relates to the Ramanujan Conjecture (RC) on the respective groups. But while for $PGL_2$ the RC holds unconditionally, this is not so in the case of $PU_3$. We find explicit cases where the RC does and does not hold, and use this to construct arithmetic non-Ramanujan Cayley bigraphs as well, and prove that nevertheless they satisfy the Sarnak-Xue density hypothesis.
On the combinatorial side, we present a pseudorandomness characterization of Ramanujan bigraphs, and a more general notion of biexpanders. We show that our Ramanujan bigraphs exhibit the cutoff phenomenon with bounded window size for non-backtracking random walks, either as a consequence of the Ramanujan property, or of the Sarnak-Xue density hypothesis. Finally, we present some other applications of our work: golden gates for $PU_3$, Ramanujan and non-Ramanujan complexes of type $\widetilde{A}_2$, optimal strong approximation for $p$-arithmetic subgroups of $PSU_3$ and vanishing of first Betti numbers of Picard modular surfaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_06507 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Ramanujan Bigraphs Evra, Shai Feigon, Brooke Maurischat, Kathrin Parzanchevski, Ori Number Theory Combinatorics Group Theory 11F70, 05C48, 20C08, 20E42, 05C81, 81P68 In their seminal paper, Lubotzky, Phillips and Sarnak (LPS) defined the notion of regular Ramanujan graphs and gave an explicit construction of infinite families of $(p+1)$-regular Ramanujan Cayley graphs, for infinitely many primes $p$. In this paper we extend the work of LPS and its successors to bigraphs (biregular bipartite graphs), in several aspects: we investigate the combinatorial properties of various generalizations of the notion of Ramanujan graphs, define a notion of Cayley bigraphs, and give explicit constructions of infinite families of $(p^3+1,p+1)$-regular Ramanujan Cayley bigraphs, for infinitely many $p$. Both the LPS graphs and our ones are arithmetic, arising as quotients of Bruhat-Tits trees by congruence subgroups of arithmetic lattices in a $p$-adic group, $PGL_2(\mathbb{Q}_p)$ for LPS and $PU_3(\mathbb{Q}_p)$ for us. In both cases the Ramanujan property relates to the Ramanujan Conjecture (RC) on the respective groups. But while for $PGL_2$ the RC holds unconditionally, this is not so in the case of $PU_3$. We find explicit cases where the RC does and does not hold, and use this to construct arithmetic non-Ramanujan Cayley bigraphs as well, and prove that nevertheless they satisfy the Sarnak-Xue density hypothesis. On the combinatorial side, we present a pseudorandomness characterization of Ramanujan bigraphs, and a more general notion of biexpanders. We show that our Ramanujan bigraphs exhibit the cutoff phenomenon with bounded window size for non-backtracking random walks, either as a consequence of the Ramanujan property, or of the Sarnak-Xue density hypothesis. Finally, we present some other applications of our work: golden gates for $PU_3$, Ramanujan and non-Ramanujan complexes of type $\widetilde{A}_2$, optimal strong approximation for $p$-arithmetic subgroups of $PSU_3$ and vanishing of first Betti numbers of Picard modular surfaces. |
| title | Ramanujan Bigraphs |
| topic | Number Theory Combinatorics Group Theory 11F70, 05C48, 20C08, 20E42, 05C81, 81P68 |
| url | https://arxiv.org/abs/2312.06507 |