| Manor Mendel z (2007) | |||||||||||||||
Abstract | |||||||||||||||
| The main question studied in this article may be viewed as a non-linear analog of Dvoretzky's Theorem in Banach space theory or as part of Ramsey Theory in combinatorics. Given a nite metric space on n points, we seek its subspace of largest cardinality which can be embedded with a given distortion in Hilbert space. We provide nearly tight upper and lower bounds on the cardinality of this subspace in terms of n and the desired distortion. Our main theorem states that for any > 0, every n point metric space contains a subset of size at least n 1 which is embeddable in Hilbert space with O | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||