Seminars & Colloquia Calendar
"A spectral gap precludes low-dimensional embeddings"
Assaf Naor, Princeton University
Location: Hill 705
Date & time: Monday, 17 April 2017 at 2:00PM -
|
|
|
|
| Time: 2:00 PM |
| Location: Hill 705 |
| Abstract: 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$. |
