01:14:44
published on March 20, 2026
Combinatoire et aléa autour des rectangulations - lecture 1
By Eric Fusy
[1188] Average distortion embeddings, nonlinear spectral gaps, and a metric John theorem
Appears in collection : Bourbaki - Janvier 2022
In this lecture we shall discuss some geometric applications of the theory of nonlinear spectral gaps. Most notably, we will present a proof of a deep theorem of Naor asserting that for any norm $|\cdot|$ on $\mathbf{R}^d$, the metric space $(\mathbf{R}^d, \sqrt{|x-y|})$ embeds into Hilbert space with quadratic average distortion $O(\sqrt{\log d})$. As a consequence, we will deduce that any n-vertex expander graph does not admit a $O(1)$-average distortion embedding into any $n^{o(1)}$-dimensional normed space.
[after Assaf Naor]
