Mixing in High-Dimensional Expanders
Mixing in High-Dimensional Expanders
复制标题
混合高维扩展器
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Ori Parzanchevski
中科院分区：
文献类型：
--
作者：
Ori Parzanchevski
我们建立了对任意（有限）简单复合物的膨胀剂混合引理的概括。原始引理指出，图的拉普拉斯光谱的浓度意味着组合膨胀（也称为混合或伪随机度）。最近，只要复合物的骨骼是完整的，就证明了这种引理的类似物的模拟。更确切地说，表明Simplicial Hodge Laplacian的浓缩光谱意味着与图中类似类型的伪随机度。在本文中，我们消除了完整骨骼的假设，表明在所有维度上同时浓度的拉普拉斯光谱浓度意味着任何复合物中的伪随机度。我们讨论各种应用程序，并提出一些空旷的问题。
We establish a generalization of the Expander Mixing Lemma for arbitrary (finite) simplicial complexes. The original lemma states that concentration of the Laplace spectrum of a graph implies combinatorial expansion (which is also referred to as mixing, or pseudo-randomness). Recently, an analogue of this lemma was proved for simplicial complexes of arbitrary dimension, provided that the skeleton of the complex is complete. More precisely, it was shown that a concentrated spectrum of the simplicial Hodge Laplacian implies a similar type of pseudo-randomness as in graphs. In this paper we remove the assumption of a complete skeleton, showing that simultaneous concentration of the Laplace spectra in all dimensions implies pseudo-randomness in any complex. We discuss various applications and present some open questions.