Expanders and Related Topics

扩展图是一个主要寻找“良好互连”的通信网络的领域。两个具有相同节点和链路数量的网络仍然可以具有非常不同的“互联性”属性；例如，如果网络中有一半的节点与另一半的连接非常少，那么这一半节点之间的通信可能会出现问题。粗略地说，扩展器是一个不会出现这种连接问题的网络。

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.