Constructing highly regular expanders from hyperbolic Coxeter groups

Abstract

A graph X is defined inductively to be (a0, . . ., an-1)-regular if X is a0-regular and for every vertex v of X, the sphere of radius 1 around v is an (a1, . . ., an-1)-regular graph. Such a graph X is said to be highly regular (HR) of level n if an-1 ≠ 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 PW,M, which form an infinite family of expander graphs when (W, S) is indefinite and PW,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.