## Notes of Ofer Neiman’s lecture

Stochastic decompositions of metric spaces

This has applications to many problems : Ramsey decompositions, distributed computing… This decompositions are a basic tool for various parts of mathematics and design of algorithms, so it is good to know how to produce them.

1. Definitions

A stochastic decomposition is a probability distribution over partitions, i.e. a random partition.

Say a partition of a metric space is ${\Delta}$-bounded if all pieces (also called clusters) have diameter ${\leq \Delta}$. Given a point ${x}$ and a partition ${P}$, ${P(x)}$ denotes the cluster that contains ${x}$.

Definition 1 Fix a positive function ${\epsilon}$ on ${X}$. Say a random ${\Delta}$-bounded partition is ${\epsilon}$-padded if, for every point ${x\in X}$,

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}(B(x,\epsilon(x)\Delta)\subseteq P(x))\geq \frac{1}{2}. \end{array}$

${\epsilon}$ will most of the time be a constant.

Example. Let ${X={\mathbb R}}$, ${\Delta=1}$. Consider the partition into integral intervals ${[i,i+1)}$ and its translates by numbers uniformly chosen in ${[0,1]}$. This is ${\epsilon}$-padded for ${\epsilon\leq 1/4}$.

Example. Let ${X=\ell_p^d=({\mathbb R}^d,\ell_p)}$, ${\Delta=1}$. The product partition is ${\epsilon}$-padded for ${\epsilon\leq \frac{1}{d\,d^{1/p}}}$.

1.2. Decomposability

Definition 2 A metric space is called ${\alpha}$-decomposable if, for every ${\Delta>0}$, there exists a ${\frac{1}{\alpha}}$-padded decomposition.

In general, every finite metric space is ${\alpha}$-decomposable with ${\alpha=O(\log(|X|))}$

Example. Planar graphs are ${\alpha}$-decomposable for a universal constant ${\alpha}$. More generally, there is a ${\alpha}$-decomposability constant for every minor-excluding family of graphs.

Example. Bounded tree-width graphs are ${\alpha}$-decomposable for a universal constant ${\alpha}$.

2. Doubling metrics

2.1. The result

Today, I will prove the following.

Theorem 3 Every bounded ${\lambda}$-doubling metric space is ${O(\log\lambda)}$-decomposable.

Doubling means finite dimensional.

Definition 4 A metric space is ${\lambda}$-doubling if for every point ${x}$ and ${r>0}$, ${B(x,2r)}$ can be covered by ${\lambda}$ balls of radius ${r}$. The doubling dimension is ${\log\lambda}$.

Example. ${\ell_p^d}$ has doubling dimension ${O(d)}$.

2.2. Proof of doubling theorem

Fix ${\Delta>0}$. Let ${N}$ be a ${\Delta/4}$-net of ${X}$. The partition will be based on balls centered at points of ${N}$. We must specify radii and an ordering of points. Choose ${r\in[\frac{\Delta}{4},\frac{\Delta}{2}]}$ uniformly at random, and choose a random ordering ${\sigma\in\mathfrak{S}_n}$.

For each ${u\in N}$, define a cluster as follows

$\displaystyle \begin{array}{rcl} C_u=\{x\in X\,;\,d(u,x)\leq r\textrm{ and }\forall v\in N\textrm{ such that }\sigma(v)<\sigma(u),\,d(v,x)>r\}. \end{array}$

The clusters of the random partition are the non empty ${C_u}$‘s.

Fix ${x\in X}$. Note that if ${u\in N}$ is such that ${d(u,x)>\Delta}$, then ${C_u\cap B(x,\frac{\Delta}{k})=\emptyset}$ where ${k=100\log\lambda>2}$. So only points in ${S=B(x,\Delta)\cap N}$ may play a role in defining the cluster of ${x}$.

Claim: ${|S|\leq \lambda^3}$. Indeed, ${B(x,\Delta)}$ can be covered by ${\lambda^3}$ balls of radius ${\frac{\Delta}{8}}$, and each of them contains at most one point of ${S}$.

One could add up brutal bounds on the effects of all points of ${S}$, but this would merely give a bound which is polynomial in ${\lambda}$. To get the logarithmic bound, one uses the randomness of the ordering. Let ${s_1,\ldots,s_m}$ be the points of ${S}$ ordered by increasing distance from ${x}$. Let ${t=\frac{\Delta}{100\log\lambda}}$. Say that ${s_j}$ cuts ${B(x,t)}$ if

1. ${s_j}$ is minimal according to the ordering ${\sigma}$ such that ${r\geq d(x,s_j)-t}$.
2. ${r\leq d(x,s_j)+t}$.

We must estimate the probability that some small ball ${B(x,t)}$ is cut, i.e. ${\mathop{\mathbb P}(B(x,t)\not\subset P(x))}$. Union bound gives

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}(B(x,t)\not\subset P(x))&\leq&\sum_{j=1}^m \mathop{\mathbb P}(s_j\textrm{ cuts }B(x,t) )\\ &=&\sum_{j=1}^m \mathop{\mathbb P}(d(x,s_j)-t\leq r\leq d(x,s_j)+t\textrm{ and }\forall i

since ${t=\frac{\Delta}{100\log\lambda}}$.

2.3. Questions

Could one apply Assouad’s embedding instead ? This would give a weaker bound, polynomial in ${\lambda}$.

How does the partition of the theorem compare with the product partition ? It does better, but it is not optimal either. Using concentration of measure, one can do even better.

Does the theorem extend to unbounded spaces ?

Tomorrow, I will explain an application of stochastic decompositions to constructing embeddings into Banach spaces, see my report.