We give new bounds on the cosystolic expansion constants of several families of high dimensional expanders, and the known coboundary expansion constants of order complexes of homogeneous geometric lattices, including the spherical building of $SL_n(F_q)$. The improvement applies to the high dimensional expanders constructed by Lubotzky, Samuels and Vishne, and by Kaufman and Oppenheim. Our new expansion constants do not depend on the degree of the complex nor on its dimension, nor on the group of coefficients. This implies improved bounds on Gromov's topological overlap constant, and on Dinur and Meshulam's cover stability, which may have applications for agreement testing. In comparison, existing bounds decay exponentially with the ambient dimension (for spherical buildings) and in addition decay linearly with the degree (for all known bounded-degree high dimensional expanders). Our results are based on several new techniques: * We develop a new "color-restriction" technique which enables proving dimension-free expansion by restricting a multi-partite complex to small random subsets of its color classes. * We give a new "spectral" proof for Evra and Kaufman's local-to-global theorem, deriving better bounds and getting rid of the dependence on the degree. This theorem bounds the cosystolic expansion of a complex using coboundary expansion and spectral expansion of the links. * We derive absolute bounds on the coboundary expansion of the spherical building (and any order complex of a homogeneous geometric lattice) by constructing a novel family of very short cones.


翻译:我们给出多个高维扩张器家族的共余单调扩展常数以及同态几何格子的阶复形的已知余边界扩展常数的新界限,包括 $SL_n(F_q)$ 的球形建筑物。改进适用于 Lubotzky,Samuels 和 Vishne,以及 Kaufman 和 Oppenheim 构建的高维扩展器。我们的新扩展常数不依赖于复形的度数或维数,也不依赖于系数群。这意味着 Gromov 的拓扑重叠常数和 Dinur 和 Meshulam 的覆盖稳定性具有改进的界限,这可能对协议测试有应用。相比之下,现有的界限随着环境维数(对于球形建筑物)和度数线性下降(对于所有已知的有界度数高维扩展器)。我们的结果基于几个新技术:我们开发了一种新的“颜色限制”技术,通过将多部分复形限制在其颜色类的小随机子集上从而证明无维数限制的扩展。我们为 Evra 和 Kaufman 的局部到全局定理提供了一种新的“谱证明”,得到更好的界限并消除了度数的依赖性。该定理使用余边界扩展和链接的谱扩展来限制复形的共余单调扩展。我们通过构造一个新的非常短的锥体家族,得到了同态几何格子(以及任何同态几何格子的阶复形)的余边界扩展的绝对界限。

0
下载
关闭预览

相关内容

【硬核书】矩阵代数基础,248页pdf
专知会员服务
88+阅读 · 2021年12月9日
专知会员服务
45+阅读 · 2020年12月18日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年5月22日
Arxiv
0+阅读 · 2023年5月19日
VIP会员
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员