Expanders, Sheaves on Graphs, and Applications

理论计算机科学产生了许多重要的问题 它可以用数学的子领域的技术来攻击，称为 线性代数。我们的建议是将一些相关技术用于 线性代数应用于“图论”，来研究这类问题。这个 线性代数与这类问题的联系是众所周知的。我们的建议 旨在加强线性代数中的已知技术，以期 它们的应用，解决了理论计算机科学中的问题。 这种技术还可以用来解决许多领域的问题 数学；事实上，计算机科学中我们感兴趣的问题是 涉及数学和物理的多个领域。在另一方 方向，这些相关领域都有研究成果，我们有时可以 借阅以加强我们对线性代数和计算机部分的知识 我们感兴趣的科学。 我们提出的研究是由理论计算机科学的两个领域推动的， 一种被称为“扩展图”，另一种被称为“复杂性理论”。这个 我们使用的线性代数的领域是“本征值”和“谱” 由“图论”到“图论”中的某些矩阵，以及与之相关的 “秸秆理论”的概念。虽然捆绑理论通常被视为一个领域 代数拓扑学，我们对层理论的兴趣在于“向量层 空间，这是一种线性代数，它的结构得到增强 一张图表。 我们对“扩展图”的研究集中在“相对扩展”上，这是一种 从较小的网络构建更大的网络的方式，以一种可以 了解大型网络在小型网络方面的扩展以及 大型网络位于较小网络之上的方式。最近有一段时间 许多新网络的结果和构造都是从较小的网络开始的。这个 相对扩张的基础始于我们2003年的一篇论文《动力》 作者Alexander Grothendieck在拓扑学和代数几何方面所做的工作。 我们对层理论的研究使我们能够比较线性代数中的结构 都位于同一张图上；这种类型的束流理论还处于初级阶段。我们 在复杂性理论的推动下开始研究这一理论，但已将其用于 解决了1950年代S关于群论的汉娜·诺依曼猜想。这 Sheaf理论的灵感来自Grothendieck和他的同事的工作。 因此，我们的项目利用了计算机领域之间富有成效的联系 科学和数学。

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.