Rutgers Discrete Mathematics Seminar

Title: A Spectral Gap Precludes Low-Dimensional Embeddings.

Speaker: Assaf Naor, Princeton University

Date: Monday, April 17, 2017 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


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>0$. This is sharp up to the value of the constant $c$, and it improves over the previously best-known estimate $mathrm{dim}(X)> c(log n)^2/D^2$.