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
专知会员服务
83+阅读 · 2021年12月9日
【硬核书】树与网络上的概率,716页pdf
专知会员服务
70+阅读 · 2021年12月8日
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
41+阅读 · 2020年12月18日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
已删除
将门创投
11+阅读 · 2019年7月4日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年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日
已删除
将门创投
11+阅读 · 2019年7月4日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员