Expanders, Sheaves on Graphs, and Applications

理论计算机科学已经产生了许多重要的问题，这些问题可以用数学的子领域线性代数的技术来解决。 我们的建议是将一些线性代数中的相关技巧应用到“图论”中，来研究这类问题。 线性代数与这类问题的联系是众所周知的。 我们的建议 * 旨在加强线性代数中的已知技术，着眼于它们的应用，以解决理论计算机科学中的问题。这些技术也可以用来解决数学领域的一些问题;事实上，我们感兴趣的计算机科学问题与数学和物理的一些领域有关。 在另一个方向，这些相关领域的研究成果，我们有时可以借用，以提高我们对线性代数和计算机科学感兴趣的部分的知识。我们提出的研究是由理论计算机科学的两个领域，* 一个被称为“扩展图”，另一个被称为“复杂性理论”。 线性代数的 * 领域，我们的工作是“特征值”和“谱 * 理论”的某些矩阵产生的“图论”，以及相关的 * 概念的“层理论”。 虽然层理论通常被视为 * 代数拓扑的一个领域，但我们对层理论的兴趣在于“向量 * 空间的层”，这是一种线性代数，它被 * 图的结构所增强。我们对“扩展图”的研究集中在“相对扩展”上，这是一种从较小的网络构建较大网络的方法，在这种方法中，人们可以理解大型网络在较小网络方面的扩展，以及大型网络位于较小网络之上的方式。 最近有很多结果和新的网络结构从较小的。 相对膨胀的基础开始于我们2003年的一篇论文，受到亚历山大格罗滕迪克在拓扑学和代数几何方面的工作的启发。我们在层理论中的研究使我们能够比较位于同一个图上的线性代数 * 中的结构;这种类型的层理论还处于起步阶段。 我们 * 开始研究这个理论的动机是复杂性理论，但已经用它来 * 解决了20世纪50年代关于群论的汉娜诺依曼猜想。 这个层理论是受到格罗滕迪克和他的同事们的工作的启发。因此，我们的项目利用计算机科学和数学领域之间富有成效的联系。

Theoretical computer science has given rise to a number of important problems***that can be attacked with techniques of the subfield of mathematics known as***linear algebra. Our proposal is to use a number of related techniques in***linear algebra applied to "graph theory", to study such problems. The***connection of linear algebra to such problems is well known. Our proposal***seeks to strengthen the known techniques in linear algebra, with a view towards***their applications, to solve problems in theoretical computer science.******Such techniques can be used also to solve problems in a number of fields of***mathematics; indeed, the problems in computer science of interest to us are***related to a number of areas of mathematics and physics. In the other***direction, these related areas have research results which we can sometimes***borrow to enhance our knowledge of the parts of linear algebra and computer***science of interest to us.******Our proposed research is motived by two areas of theoretical computer science,***one known as "expander graphs", another known as "complexity theory". The***areas of linear algebra that we work with are the "eigenvalues" and "spectral***theory" of certain matrices arising in to "graph theory", and the related***notion of "sheaf theory". While sheaf theory is often viewed as a field of***algebraic topology, our interest in sheaf theory is in "sheaves of vector***spaces," which is a type of linear algebra that is enhanced by the structure of***a graph.******Our research in "expander graphs" focuses on "relative expansion," which is a***way of building larger networks from smaller ones, in a way where one can***understand expansion of the large network in terms of the smaller network and***the way the large network lies "over" the smaller one. Recently there has been***a lot of results and constructions of new networks from smaller ones. The***foundations of relative expansion began in a paper of ours from 2003, motivated***by work of Alexander Grothendieck in topology and algebraic geometry.******Our research in sheaf theory allows us to compare structures in linear algebra***that lie over the same graph; this type of sheaf theory is in its infancy. We***began to study this theory motivated by complexity theory, but have used it to***solve the Hanna Neumann Conjecture of the 1950's regarding group theory. This***sheaf theory was inspired by work of Grothendieck and his colleagues.******Hence our project exploits the fruitful connection between areas of computer***science and mathematics.