Constructing highly regular expanders from hyperbolic Coxeter groups

Abstract:

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 [Combinatorica 40 (2020), pp. 473–509] studied HR-graphs of level $2$ and provided several methods to construct families of graphs which are expanders “globally and locally”, and asked about the existence of HR-graphs of level $3$.

In this paper we show how the theory of Coxeter groups, and abstract regular polytopes and their generalisations, can be used to construct 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.