tailieunhanh - Đề tài " On metric Ramsey-type phenomena "

The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky’s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite 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 n1−. | Annals of Mathematics On metric Ramsey-type phenomena By Yair Bartal Nathan Linial Manor Mendel and Assaf Naor Annals of Mathematics 162 2005 643 709 On metric Ramsey-type phenomena By Yair Bartal Nathan Linial Manor Mendel and Assaf Naor Abstract The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite 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 e 0 every n point metric space contains a subset of size at least n1-e which is embeddable in Hilbert space with O log e distortion. The bound on the distortion is tight up to the log 1 e factor. We further include a comprehensive study of various other aspects of this problem. Contents 1. Introduction . Results for arbitrary metric spaces . Results for special classes of metric spaces 2. Metric composition . The basic definitions . Generic upper bounds via metric composition 3. Metric Ramsey-type theorems . Ultrametrics and hierarchically well-separated trees . An overview of the proof of Theorem . The weighted metric Ramsey problem and its relation to metric composition . Exploiting metrics with bounded aspect ratio . Passing from an ultrametric to a fe-HST . Passing from a fe-HST to metric composition . Distortions arbitrarily close to 2 4. Dimensionality based upper bounds 5. Expanders and Poincare inequalities 6. Markov type girth and hypercubes . Graphs with large girth . The discrete cube 644 YAIR BARTAL NATHAN LINIAL MANOR MENDEL AND ASSAF NAOR 1. Introduction The philosophy of modern Ramsey theory states that large systems necessarily contain large highly structured sub-systems. The classical .