Abstract: Expander graphs are sparse graphs with strong connectivity properties. Chapman, Linial and Peled asked whether there exist families of expander graphs with high levels of regularity, that is not only the number of edges containing a given vertex needs to be constant but also the number of triangles containing a given edge etcetera. We answer this question positively constructing families of expander graphs as quotient graphs of 1-skeleta of infinite polytopes (1-skeleton means only retain the vertex-edge information of the polytope). The latter are Wythoffian polytopes, which are obtained from Coxeter groups by decorating the associated Coxeter diagram. The specific higher regularity properties depend on this diagram. Expansion stems from superapproximation of the Cayley graphs associated to the Coxeter group, which is a number-theoretic way to study the rate of convergence of random walks on these graphs. The Cayley graphs and the 1-skeleta are quasi-isometric (that is equal on a large scale) which implies that one forms an expanding family if and only if the other does. 

Based on joint work with Marston Conder, Alexander Lubotzky and Francois Thilmany.