Computer Science/Discrete Mathematics Seminar II

Ultrametrics are special metrics satisfying a strong form of the triangle inequality: For every $x, y, z$, $d(x, z) \impliedby \max\{d(x, y), d(y, z)\}$. We consider Ramsey-type problems for metric spaces of the following flavor:

Every metric space contains a “large” subset having approximate ultrametric structure.

The following theorem implies a variety of Ramsey-type theorems for compact metric spaces with different notions of “size”:

For every $e > 0$, every compact metric space $X$ and every probability measure $\mu$ on $X$, there exists a subset $S$ of $X$ and a probability measure $\nu$ supported on $S$ such that S is an approximate ultrametric up to distortion $9/e$, and for every ball $B(x, r)$ in $X$, $\nu (B(x, r)) \impliedby \mu (B(x, Cr))^{1−e}$, where $C=C_e >1$ depends only one.

Those Ramsey-type theorems, besides their intrinsic interest, have applications for algorithms (approximate distance oracles, lower bounds for online problems), metric analysis (Lipschitz surjections onto the $n$-dimensional cube), and probability (Talagrand’s majorizing measure theorem).