Using hyperbolic Coxeter groups to construct highly regular expander graphs

A graph $X$ is defined inductively to be $(a_0, . . . , 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, . . . , a_{n−1})$-regular graph. A family $F$ of graphs is said to be an expander family if there is a uniform lower bound on the Cheeger constant of all the graphs in $F$. 

After briefly (re)introducing Coxeter groups and their geometries, we will describe how they can be used to construct very regular polytopes, which in turn can yield highly regular graphs. We will then use the super-approximation machinery, whenever the Coxeter group is hyperbolic, to obtain the expansion of these families of graphs. As a result, we obtain interesting infinite families of highly regular expander graphs, some of which are related to the exceptional groups. 

The talk is based on work joint with Conder, Lubotzky, and Schillewaert.