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$.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math