Assaf Naor

Abstract: A spectral gap precludes low-dimensional embeddings

We prove that if an n-vertex O(1)-expander graph embeds with average distortion D into a finite dimensional normed space X, then necessarily the dimension of X is at least n^{c/D} for some universal constant c bigger than 0. This is sharp up to the value of the constant c, and it improves over the previously best-known estimate dim(X)\geq c(logn)^2/D^2. The proof relies on a probabilistic argument, namely the behavior of Markov chains in spaces obtained from complex interpolation.