Expanders and related topics

当在通信网络上存在大量业务时，网络可能发展“热点”，即存在“大量”分组（消息、电话呼叫等）的链路（边缘）。他们想使用这个链接。 一种类型的网络或图不会发生这种情况（给定一个好的路由策略），这种类型的图被称为“扩展器”。扩展器在计算机科学理论中有大量的应用，包括随机性、路由和其他领域。 构建它们的问题（即给出显式构造）在计算机科学理论和数学界引起了很多关注。 尽管仍有一些令人信服的问题尚未解决，但在显式构造扩张子方面已经取得了重大进展;这些进展中的大部分都使用了扩张子与图的邻接矩阵的线性代数之间的重要联系，即其特征值。本项目旨在进一步研究扩张子及其与图的邻接矩阵的线性（和非线性）代数之间的关系。

When there is a lot of traffic on a communication network, the network may develop "hot spots," i.e. links (edges) where there is a "large" number of packets (messages, phone calls, etc.) which want to use that link.  A type of network or graph where this does not happen (given a good routing strategy) is a type of graph known as an "expander."Expanders have a large number of applications to computer science theory, including to randomness, routing, and other areas.  The problem of building them (i.e. giving explicit constructions) has drawn a lot of attention in the computer science theory and mathematics communities.  There has been significant progress towards explicitly constructing expanders, although a number of compelling problems remain open; much of this progress uses an important connection between expanders and the linear algebra of the graph's adjacency matrix, namely its eigenvalues.This project aims to further study expanders and their relationships to the linear (and non-linear) algebra of the graph's adjacency matrix.