Dichotomies, structure, and concentration in normed spaces

We use probabilistic, topological and combinatorial methods to establish the following deviation inequality: For any normed space X=(Rn,‖⋅‖) there exists an invertible linear map T:Rn→Rn withP(|‖TG‖−E‖TG‖|>εE‖TG‖)≤Cexp⁡(−cmax⁡{ε2,ε}log⁡n),ε>0, where G is the standard n-dimensional Gaussian vector and C,c>0 are universal constants. It follows that for every ε∈(0,1) and for every normed space X=(Rn,‖⋅‖) there exists a k-dimensional subspace of X which is (1+ε)-Euclidean and k≥cεlog⁡n/log⁡1ε. This improves by a logarithmic on ε term the best previously known result due to G. Schechtman.