High Dimensional Expanders and Ramanujan Complexes

在过去的四十年里，扩展图一直是数学和计算机科学研究的焦点。这些稀疏但高度连通的图在建立通信网络、计算机算法和纠错码理论中都是非常重要的。扩展图的研究一直在借鉴深奥的数学工具，如数论、表示论和拓扑学。近年来，对展开器的研究也给纯数学家提出了新的问题。数学和计算机科学的这种相互作用是非常有成效的。目前的建议旨在通过启动对高维膨胀剂的系统研究来进一步发展膨胀剂理论，高维膨胀剂是具有类似膨胀剂性质的高维简单复合体。高维情况下的问题比较困难，但我们希望发展的理论在应用上可以预期是强大的。具体地说，PI计划考虑各种方式来扩展扩展器的定义，例如，通过谱、上同调或拓扑。特别令人感兴趣的是Ramanujan复合体，它推广了Ramanujan图。它们的极值性质(用表示论和数论的方法证明)和它们显著的对称性有望在解决几个问题时有用。格罗莫夫的拓扑重叠性质特别重要。人们希望Ramanujan复形的极值性质将有助于解决纠错码理论中以及计算机科学的其他领域中的一些基本问题。

Expander graphs have been a focus of study in mathematics and computer science during the last four decades. These sparse and yet highly connected graphs are of fundamental importance in building communication networks, in computer algorithms, and in the theory of error-correcting codes. The study of expander graphs has been drawing tools from deep mathematics, such as number theory, representation theory, and topology. In recent years the study of expanders also provided new problems for pure mathematicians. This interplay of mathematics and computer science has been very productive. The current proposal aims at taking the theory of expanders one step further by initiating a systematic study of high-dimensional expanders, which are simplical complexes of high dimensions having similar properties of expanders. The problems in the high-dimensional case are more difficult, but the theory we hope to develop can be expected to be powerful in applications. Specifically, the PIs plan to consider various ways to extend the definition of expanders, e.g., via spectrum, cohomology or topology. Of particular interest are the Ramanujan complexes, which generalize the Ramanujan graphs. Their extremal properties (proved by methods of representation theory and number theory) together with their remarkable symmetry are expected to be useful in solving several problems. Of special importance is Gromov's topological overlapping property. It is hoped that the extremal properties of Ramanujan complexes will help resolve some problems of basic importance in the theory of error-correcting codes, as well as in other areas of computer science.