Expander graphs have been a focus of study in mathematics and computer science during the last four decades. These sparse and yet highly connected graphs are of fundamental importance in building communication networks, in computer algorithms, and in the theory of error-correcting codes. The study of expander graphs has been drawing tools from deep mathematics, such as number theory, representation theory, and topology. In recent years the study of expanders also provided new problems for pure mathematicians. This interplay of mathematics and computer science has been very productive. The current proposal aims at taking the theory of expanders one step further by initiating a systematic study of high-dimensional expanders, which are simplical complexes of high dimensions having similar properties of expanders. The problems in the high-dimensional case are more difficult, but the theory we hope to develop can be expected to be powerful in applications.
Specifically, the PIs plan to consider various ways to extend the definition of expanders, e.g., via spectrum, cohomology or topology. Of particular interest are the Ramanujan complexes, which generalize the Ramanujan graphs. Their extremal properties (proved by methods of representation theory and number theory) together with their remarkable symmetry are expected to be useful in solving several problems. Of special importance is Gromov's topological overlapping property. It is hoped that the extremal properties of Ramanujan complexes will help resolve some problems of basic importance in the theory of error-correcting codes, as well as in other areas of computer science.
