Minerva Lecture III: Super-expanders and nonlinear spectral calculus

-
Assaf Naor, Courant Institute, NYU
McDonnell Hall A01

While the topic of this talk initially arose in the context of the Ribe program, it will take us further afield. A bounded degree n-vertex graph $G = (V, E)$ is an expander if and only if for every choice of $n$ vectors ${x_v}_{v\in V}$ in $R^k$ the average of the Euclidean distance between $x_u$ and $x_v$ is within a constant factor of the average of the same terms over those pairs ${u, v}$ that form an edge in $E$. The fact that this property is equivalent to the usual combinatorial notion of graph expansion is very simple to prove, and once stated, it is obvious to ask what happens when $R^k$ is replaced by other metric spaces. It turns out that this is a subtle question that relates to a long line of investigations in analysis and geometry. Graphs that are expanders in the classical sense (including random graphs) may or may not be expanders with respect to certain non-Euclidean geometries of interest. Existence of such "metric" expanders becomes a delicate question due in part to the fact that the existing combinatorial, probabilistic and spectral methods that are used for the purpose of constructing classical expanders are insufficient in the metric setting. In this talk we will formulate some of the basic questions in this direction and explain some of the ideas and methods that were introduced in order to address them.

Event Video