Ramanujan Complexes and Bounded Degree Topological Expanders
Ramanujan Complexes and Bounded Degree Topological Expanders
复制标题
拉马努金复合体和有界度拓扑展开器
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Lubotzky
中科院分区：
文献类型：
--
作者：
T. Kaufman;D. Kazhdan;A. Lubotzky
在过去的四十年里，扩展图一直是计算机科学领域关注的焦点。近年来，一种关于扩张器的高维理论正在兴起。将展开理论推广到单纯复形有几种可能，其中突出的是余边界展开和拓扑展开子。众所周知，对于每个d，都有无界的维d的单纯复形，它们具有这些性质。然而，Gromov提出的一个主要公开问题是，根据这些定义，d&ge；2是否存在有界次高维扩张子。我们给出了高维扩张子d=2的有界次复形的一个显式构造。更准确地说，我们的主要结果表明，三维Ramanujan络合物的2-骨架是拓扑扩张器。假设Serre关于同余子群性质的一个猜想，它们中的无穷多个也是余边界扩张子。
Expander graphs have been a focus of attention in computer science in the last four decades. In recent years a high dimensional theory of expanders is emerging. There are several possible generalizations of the theory of expansion to simplicial complexes, among them stand out coboundary expansion and topological expanders. It is known that for every d there are unbounded degree simplicial complexes of dimension d with these properties. However, a major open problem, formulated by Gromov, is whether bounded degree high dimensional expanders, according to these definitions, exist for d ≥ 2. We present an explicit construction of bounded degree complexes of dimension d = 2 which are high dimensional expanders. More precisely, our main result says that the 2-skeletons of the 3-dimensional Ramanujan complexes are topological expanders. Assuming a conjecture of Serre on the congruence subgroup property, infinitely many of them are also coboundary expanders.