摘要：We prove that if an n-vertex O(1)-expander 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 dim(X)> c(log n)^2/D^2 of Linial, London and Rabinovich, strengthens a theorem of Matousek, and answers a question of Andoni, Nikolov, Razenshteyn and Waingarten.
