Expanders and Related Topics

扩展图是一个本质上寻求找到“良好互连”的通信网络的领域。具有相同数量节点和链路的两个网络仍然可以具有非常不同的“互连性”属性;例如，如果网络的某一半节点与另一半节点之间的链路非常少，则两半之间的通信可能会出现问题。粗略地说，扩展器是不会发生这种连接问题的网络。 图的扩张性质可以通过图的邻接矩阵的特征值来研究。这种通过线性代数来研究连通性或“几何”性质的方法非常成功。此外，理论计算机科学和数学中使用的结构的其他组合性质可以通过相关的线性代数和矩阵来理解，特别是它们的特征值结构。 这个项目的一个主题是尝试使用不同的数学工具--通常与扩展图和理论计算机科学无关的工具--来获得对扩展器的新见解。因此，参与这个项目的研究人员，特别是学生和博士后，通常必须花费大量的时间学习新的数学领域，即使他们已经熟悉扩展器的基础知识。这意味着我们的项目在所需的背景方面有很高的“启动”成本;我们相信这个高成本是我们所取得的成就所证明的。 这些成就包括证明了阿隆猜想，它给出了随机扩展器的最佳界限，并且在许多情况下，给出了某类扩展器的最佳界限。另一个成就是证明了著名的汉娜·诺依曼猜想，这是20世纪50年代数学领域的一个猜想;我们用我们设计来研究复杂性理论的技术证明了这一点。因此，这个项目展示了理论计算机科学和不同数学领域之间的交叉施肥。

Expander graphs is a field that essentially seeks to find communication networks that are "well interconnected." Two networks with the same number of nodes and links can still have very different "interconnectivity" properties; for example, if some half of the nodes of a network have very few links to the other half, communication between the two halves can be problematic. Roughly speaking, an expander is a network in which such connectivity issues do not occur. The expansion properties of a graph can be studied via the eigenvalues of the graph's adjacency matrix. This approach to connectivity or "geometric" properties via linear algebra has been very successful. Furthermore, other combinatorial properties of structures used in theoretical computer science and mathematics can be understood via associated linear algebra and matrices, especially their eigenvalue structure. One theme of this project is to try to use diverse mathematical tools--tools not usually associated with expanding graphs and theoretical computer science--to gain new insight into expanders. Thus the researchers involved with this project--especially students and postdocs--often must spend substantial amounts of time learning new areas of mathematics, even if they are already familiar with the basics of expanders. This means that our project has a high "start up" cost in terms of required background; we believe this high cost is justified by the achievements we have made. These achievements include proving the Alon Conjecture, that gives the best bounds on random expanders and the, in many cases, the best bound on any expander in a certain class. Another achievement has been to prove the well known Hanna Neumann Conjecture, a conjecture of the 1950's in a field of mathematics; we proved this with techniques we designed to study complexity theory. This project hence demonstrates a cross fertilization between theoretical computer science and diverse mathematical fields.