Abstract: Expander graphs have played an important role, in the last four decades, in many areas of computer science. Recently they have already found applications in pure mathematics. We describe some of this history and present in these three talks some recent efforts to build a high-dimensional theory of expanders. We will start with Gromov’s geometric and topological expanders.
Abstract: Ramanujan graphs are optimal expanders. Their explicit construction is based on deep results of Deligne and Drinfeld in the theory of automorphic forms of \(GL(2)\). The work of Lafforgue for \(GL(d)\) enables the developments of high-dimensional objects: the Ramanujan complexes. These simplical complexes/hyper graphs enjoy some remarkable properties, being random-like but at the same time very symmetric. We will show how this helps to solve some problems in computer science (e.g., error-correcting codes) and in geometry.
Abstract: Another direction of generalizing expanders from graphs to simplical complexes was proposed independently by Linial-Meshulam (in the context of developing Erodos-type theory of random simplical complexes) and by Gromov (when studying overlapping properties). We explain this notion and show a surprising connection with “property testing” which is a subject of fundamental importance, in theory and practice, in computer science.
Virginia Mathematics Lectures archive