Constructing highly regular expanders from hyperbolic Coxeter groups
Constructing highly regular expanders from hyperbolic Coxeter groups
复制标题
从双曲 Coxeter 群构建高度规则的展开器
DOI：
10.1090/tran/8456
复制
发表时间：
2020
影响因子：
1.3
通讯作者：
Franccois Thilmany
中科院分区：
文献类型：
--
作者：
M. Conder;A. Lubotzky;J. Schillewaert;Franccois Thilmany
如果 $X$ 是 $a_0$-正则图，并且对于 $X$ 的每个顶点 $v$，围绕 $v$ 半径为 $1$ 的球体是一个 $(a_1,\dots,a_{n-1})$-正则图，则图 $X$ 被归纳定义为 $(a_0,\dots,a_{n-1})$-正则图。如果 $a_{n-1}\neq 0$，则这样的图 $X$ 被认为是 $n$ 级的高度正则 (HR)。 Chapman、Linial 和 Peled 研究了 2 级 HR 图，并提供了几种构建图族的方法，这些图族是“全局和局部”的扩展器。他们询问这样的 3 级 HR 图是否存在。
在本文中，我们展示了考克塞特群理论、抽象正则多胞形及其概括如何得出这样的图。给定 Coxeter 系统 $(W,S)$ 和 $S$ 的子集 $M$，我们构造关联的 Wythoffian 多胞体 $\mathcal{P}_{W,M}$ 的 1-骨架的高度正则商，当 $(W,S)$ 不定并且 $\mathcal{P}_{W,M}$ 具有有限顶点链接时，它们形成无限的扩展图族。该族中图的规律性可以从 $(W,S)$ 的 Coxeter 图推导出来。展开源于对线性群 $W$ 的同余子群应用超近似。
该机器提供了丰富的 HR 图系列，具有各种有趣的特性，特别是肯定地回答了 Chapman、Linial 和 Peled 提出的问题。
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.