The EMS Publishing House is now **EMS Press** and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

# Journal of the European Mathematical Society

Full-Text PDF (242 KB) | Metadata | Table of Contents | JEMS summary

**Volume 9, Issue 2, 2007, pp. 253–275**

**DOI: 10.4171/JEMS/79**

Published online: 2007-06-30

Ramsey partitions and proximity data structures

Manor Mendel^{[1]}and Assaf Naor

^{[2]}(1) The Open University of Israel, Raanana, Israel

(2) New York University, United States

This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman in~\cite{BFM86}). We then proceed to construct optimal Ramsey partitions, and use them to show that for every $\e\in (0,1)$, every $n$-point metric space has a subset of size $n^{1-\e}$ which embeds into Hilbert space with distortion $O(1/\e)$. This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor~\cite{BLMN05}, in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick in~\cite{TZ05}. Namely, we show that for every $n$ point metric space $X$, and $k\geq 1$, there exists an $O(k)$-approximate distance oracle whose storage requirement is $O\left( n^{1+1/k}\right)$, and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking.

*Keywords: *Metric Ramsey theorem, approximate distance oracle, proximity data structure

Mendel Manor, Naor Assaf: Ramsey partitions and proximity data structures. *J. Eur. Math. Soc.* 9 (2007), 253-275. doi: 10.4171/JEMS/79