nucleation

LIT-1161: On Lipschitz embedding of finite metric spaces in Hilbert space

1 min read

Properties4
StatusUnavailable — unread, registered 2026-10-16. A lawful copy was sought and not reached: OpenAlex lists only the closed Springer version, and web searches found no author-posted or course-hosted copy. Its theorem is restated and its proof scheme used by Linial, London and Rabinovich (LIT-1155), which is how the record reads it until a copy is supplied.
Tagsmathematics
Extended byLIT-1155 — The geometry of graphs and some of its algorithmic applications
Cited as “source” byTHEORY-394 — Every n-point metric space embeds in Euclidean space of O(log n) dimensions with distortion O(log n), by distances to random sets of every scale followed by Johnson–Lindenstrauss, and constant-degree expanders need distortion Ω(log n) in every ℓ_p with 1 ≤ p ≤ 2, of any dimension, so O(log n) is tight in the worst case; the constants are unspecified, the lower bound rests on Leighton and Rao's flow–cut gap, and nothing is shown for trees or for p > 2

Graph View

Jean Bourgain (1985), “On Lipschitz embedding of finite metric spaces in Hilbert space”, Israel Journal of Mathematics 52(1–2): 46–52 — doi:10.1007/BF02776078

Key takeaways

Unread. From citing works, to be checked against the text.

  • O(log n) distortion. Every n-point metric space embeds into ℓ₂ with distortion O(log n), as citing works state it. The abstract, as search results quote it, also gives an example showing a matching lower bound of a weaker order, and calls the methods probabilistic.

Standing in the record

Filed on 2026-10-16 as the result Johnson and Lindenstrauss’s Problem 4 asked about (NOTE-930), and as the source of “Bourgain’s theorem”, which the hyperbolic-embeddings reading cites through Linial, London and Rabinovich (NOTE-679). Read through LIT-1155 until a copy is supplied.

Backlinks