Constructing highly regular expanders from hyperbolic Coxeter groups

Autor: Jeroen Schillewaert, Alexander Lubotzky, François Thilmany, Marston Conder
Přispěvatelé: UCL - SST/IRMP - Institut de recherche en mathématique et physique
Rok vydání: 2021
Předmět:
Zdroj: Transactions of the American mathematical society, Vol. np, no.np, p. 22 (2020)
ISSN: 1088-6850
0002-9947
DOI: 10.1090/tran/8456
Popis: A graph $X$ is defined inductively to be $(a_0,\dots,a_{n-1})$-regular if $X$ is $a_0$-regular and for every vertex $v$ of $X$, the sphere of radius $1$ around $v$ is an $(a_1,\dots,a_{n-1})$-regular graph. Such a graph $X$ is said to be highly regular (HR) of level $n$ if $a_{n-1}\neq 0$. Chapman, Linial and Peled studied HR-graphs of level 2 and provided several methods to construct families of graphs which are expanders "globally and locally". They ask whether such HR-graphs of level 3 exist. In this paper we show how the theory of Coxeter groups, and abstract regular polytopes and their generalisations, can lead to such graphs. Given a Coxeter system $(W,S)$ and a subset $M$ of $S$, we construct highly regular quotients of the 1-skeleton of the associated Wythoffian polytope $\mathcal{P}_{W,M}$, which form an infinite family of expander graphs when $(W,S)$ is indefinite and $\mathcal{P}_{W,M}$ has finite vertex links. The regularity of the graphs in this family can be deduced from the Coxeter diagram of $(W,S)$. The expansion stems from applying superapproximation to the congruence subgroups of the linear group $W$. This machinery gives a rich collection of families of HR-graphs, with various interesting properties, and in particular answers affirmatively the question asked by Chapman, Linial and Peled.
Comment: 22 pages, 2 tables. Dedicated to the memory of John Conway and Ernest Vinberg
Databáze: OpenAIRE
Externí odkaz: