Low dimensional embeddings of ultrametrics

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Research output: Contribution to journalArticle

11 Scopus citations

Abstract

In this note we show that every n-point ultrametric embeds with constant distortion in ℓpO(logn) for every ∞≥p≥1. More precisely, we consider a special type of ultrametric with hierarchical structure called a k-hierarchically well-separated tree (k-HST). We show that any k-HST can be embedded with distortion at most 1+O(1/k) in ℓp O(k2logn). These facts have implications to embeddings of finite metric spaces in low dimensional ℓp spaces in the context of metric Ramsey-type theorems.

Original languageEnglish (US)
Pages (from-to)87-92
Number of pages6
JournalEuropean Journal of Combinatorics
Volume25
Issue number1
DOIs
StatePublished - Jan 1 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Keywords

  • Metric embeddings
  • Ultrametrics

Fingerprint Dive into the research topics of 'Low dimensional embeddings of ultrametrics'. Together they form a unique fingerprint.

  • Cite this