Expanders and Related Topics

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

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.