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.