A tight threshold for metric Ramsey phenomena

ABSTRACT

In this paper, we examine the metric Ramsey problem for the normed spaces lp: given some 1 ≤ p ≤ ∞, α ≥ 1 and an integer n, we ask for the largest m such that every n-point metric space contains an m-point subspace which embeds into lp with distortion at most α. Bartal, Linial, Mendel and Naor show in [3] that in the case of 1 ≤ p ≤ 2, the dependence of m on α undergoes a phase transition at α = 2. The case of p > 2 was left as an open problem. We show that the phase transition occurs around α = 2 for all p ≥ 1. The basis of our result is a proof that there exist {1, 2} metrics which require distortion arbitrarily close to 2 for embedding into lp. In order to show this, we develop new tools for analyzing embeddings of random metrics into lp.

REFERENCES

• 1: Y. Bartal, B. Bollobás, M. Mendel. Ramsey-type theorems for metric spaces with applications to online problems, 2002. To appear in Special Issue of Journal of Computer and System Science. http://www.cs.huji.ac.il/mendelma/mypapers.
• 2: Yair Bartal , Nathan Linial , Manor Mendel , Assaf Naor, On metric ramsey-type phenomena, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780610]
• 3: Yair Bartal , Nathan Linial , Manor Mendel , Assaf Naor, Some Low Distortion Metric Ramsey Problems, Discrete & Computational Geometry, v.33 n.1, p.27-41, January 2005 [doi>10.1007/s00454-004-1100-z]
• 4: Avrim Blum , Howard Karloff , Yuval Rabani , Michael Saks, A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems, SIAM Journal on Computing, v.30 n.5, p.1624-1661, 2000 [doi>10.1137/S0097539799351882]
• 5: J. Bourgain, T. Figiel, V. Milman. On Hilbertian subsets of finite metric spaces. In Israel Journal of Mathematics 55(2), pages 147--152, 1986.
• 6: A. Dvoretzky. Some results on convex bodies and Banach spaces. In Proceedings of the International Symposium on Linear Spaces (Jerusalem, 1960), pages 123--160. Jerusalem Academic Press, Jerusalem, 1961.
• 7: P. Indyk and J. Matoušek. Low-distortion embeddings of finite metric spaces, chapter 8 in the forthcoming CRC Handbook of Discrete and Computational Geometry, second edition.
• 8: Howard Karloff , Yuval Rabani , Yiftach Ravid, Lower Bounds for Randomized $k$-Serverand Motion-Planning Algorithms, SIAM Journal on Computing, v.23 n.2, p.293-312, April 1994 [doi>10.1137/S0097539792224838]
• 9: N. Linial. Finite Metric Spaces - Combinatorics, Geometry and Algorithms. In Proceedings of the International Congress of Mathematicians III pages 573--586, 2002.
• 10: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 11: J. Matoušek. On Embedding Expanders into lp spaces. In Israel Journal of Mathematics 102, pages 189--197, 1997.
• 12: J. Matoušek. Open Problems on Embeddings of Finite Metric Spaces at http://kam.mff.cuni.cz/matousek/haifaos.ps