Notes of Daniel Galicer’s lecture

The minimal distortion needed to embed a binary tree into ${\ell^p}$

I will cover theorems very similar to those in the previous talk, but the methods will be different, with a more combinatorial flavour.

1. Ramsey theory

1.1. Friends and strangers problem

How many people should be in a party in order to ensure that at least 3 of them know each other or at least three of them were strangers ?

View the ${n}$ participants as a complete graph some of whose edges are coloured. We want a triangle painted in one single colour.

The answer is ${n=6}$.

1.2. Ramsey’s theorem

Theorem 1 (Ramsey) Given ${r}$, ${s\in{\mathbb N}}$, there exists ${R(r,s)}$ such that if ${n\geq R(r,s)}$, in any graph with ${n}$ vertices, there exists either an ${r}$-clique (complete subgraph) or an ${s}$-independent set (no edges between them).

We just saw that ${R(3,3)=6}$. It is known that ${R(4,4)=18}$.

\indent{If aliens would threaten Earth of war unless we can give them the value of ${R(5,5)}$, we should put all our efforts to find it. If they would ask for ${R(6,6)}$, we should better get ready for war (Erdos).}

So do not think that these numbers are easy to compute. Finding rough estimates on them is a theory in itself.

2. Ramsey and embeddings

2.1. Embedding trees into ${p}$-convex Banach spaces

See Li’s lecture for the definition of ${p}$-convexity. Hilbert space is 2-convex. ${L^p}$ is ${p}$-convex if ${p\geq 2}$ and 2-convex if ${1.

Theorem 2 Let ${X}$ be a ${p}$-convex Banach space. Let ${B_n}$ be the complete rooted binary tree of depth ${n}$. For any embedding ${f:B_n\rightarrow X}$,

$\displaystyle \begin{array}{rcl} dist(f)\geq\Omega((\log n)^{1/p}). \end{array}$

2.2. Hanner’s inequality

If ${p>2}$,

$\displaystyle \begin{array}{rcl} (|x|+|y|)^p +||x|-|y||^p \geq |x+y|^p+|x-y|^p\geq 2(|x|^p+|y|^p). \end{array}$

If ${p<2}$, the inequalities are reversed.

2.3. Forks

A 4-tuple of points ${\{x_0,x_1,x_2,x'_2\}}$ is a ${\delta}$-fork if ${\{x_0,x_1,x_2\}}$ and ${\{x_0,x_1,x'_2\}}$ are ${(1+\delta)}$-isomorphic to ${\{0,1,2\}}$ (mapping ${x_1}$ to 1).

Lemma 3 In a ${p}$-convex Banach space, ${p\geq 2}$, every ${\delta}$-fork satisfies

$\displaystyle \begin{array}{rcl} |x_2-x'_2|=|x_0-x_1|O(\delta^{1/p}). \end{array}$

Proof. One can assume that ${x_0=0}$, ${|x_1|=1}$. Let

$\displaystyle \begin{array}{rcl} z:=x_1+\frac{x_2-x_1}{|x_2-x_1|}. \end{array}$

Then ${|z-x_1|=1}$, ${|z-x_2|\leq 2\delta}$. Apply ${p}$-convexity inequality to unit vectors ${x=x_1}$ and ${y=z-x_1}$. Their midpoint is ${\frac{z}{2}}$, and ${|\frac{z}{2}|\geq 1-\delta}$. Therefore ${|x-y|\leq C\,\delta^{1/p}}$. Furthermore,

$\displaystyle \begin{array}{rcl} |x_2-2x_1|\leq |x_2-z|+|z-2x_1|=O(\delta^{1/p}),\quad |x'_2-2x_1|=O(\delta^{1/p}), \end{array}$

thus ${|x_2-x'_2|=O(\delta^{1/p})}$.

2.4. Combinatorics in rooted trees

Let ${T}$ be a rooted tree. Let ${SP(T)}$ denote the set of pairs ${(x,y)}$ of vertices with ${x}$ on the path from the root to ${y}$.

Denote by ${T_{k,h}}$ denote the complete ${k}$-ary tree of depth ${h}$.

Lemma 4 Let ${k\geq r^{(h+1)^2}}$. Colour ${SP(T_{k,h})}$ in ${r}$ colours. Then there is a copy ${T'}$ of ${B_h}$ such that the colour of any pair ${(x,y)\in SP(T')}$ only depends on the levels of ${x}$ and ${y}$.

Claim. It the leaves of ${T_{k,h}}$ are coloured by ${r'}$ colours and ${k>r'}$, then there is a copy of ${B_h}$ inside ${T_{k,h}}$ with monochromatic leaves.

This is proven by induction on ${h}$. Below the root, there are ${k}$ trees isomorphic to ${T_{k,h-1}}$. By induction, in each of them, there is a binary subtree ${B_{h-1}}$ with monocoloured leaves. Since ${k>r'}$, two of these binary subtrees have the same leaf colour. Connect them via the root, this yields a binary subtree ${B_h}$ with monocoloured leaves.

Back to the proof of the Lemma. We label each leaf ${z}$ of ${T_{k,h}}$ by a vector whose components are the colours of the ${\frac{h(h+1)}{2}}$ successive pairs ${(x,y)}$ along the path from ${o}$ to ${z}$. So the number of labels is ${r'< r^{(h+1)^2}\leq k}$. According to the Claim, there is a binary subtree ${B_h}$ with monocoloured leaves, meaning that colours of pairs depend only on their depths.

2.5. Matousek’s proof of the Theorem

We shall use the following easy facts.

Lemma 5 ${T_{k,h}}$ embeds into ${B_n}$ for ${n=2h[\log_2 k]}$.

Lemma 6 (Path embedding lemma) Given ${\alpha}$, ${\beta\in(0,1)}$, there exists ${C}$ such that every distance non decreasing map

$\displaystyle \begin{array}{rcl} f:\{0,1,\ldots,h\}\rightarrow M \end{array}$

in some metric space ${M}$, with ${h\geq 2^{CK^{\alpha}}}$, ${K=Lip(f)}$, there exists an arithmetic progression

$\displaystyle \begin{array}{rcl} Z=\{x,x+a,x+2a\} \end{array}$

such that the restriction of ${f}$ to ${Z}$ is ${(1+\epsilon)}$-isometric, for ${\epsilon=\epsilon(\alpha,\beta,a)}$.

Let ${f:B_n\rightarrow X}$ be a distance non decreasing map, of distorsion ${K=(\log n)^{1/p}}$. We shall look for forks in the image. We start with a complete ${k}$-ary subtree ${T_{k,h}}$ of ${B_n}$. We colour the elements of ${SP(T_{k,h})}$ according to the distorsion of ${f}$: the colour is the integer part of

$\displaystyle \begin{array}{rcl} \lfloor\frac{K^p}{\beta}\frac{|f(x)-f(y)|}{d_{T_{k,h}}(x,y)}\rfloor, \end{array}$

${\beta}$ a small constant.

Thanks to our Ramsey type Lemma, we find a complete binary subtree ${B_h}$ in ${T_{k,h}}$ with nodes coloured by their depth only. Along each path from root to a leaf, we find an arithmetic progression ${\{y_0,y_1,y_2\}}$ of step ${a}$ along which ${f}$ is nearly isometric. Let ${y'_2}$ be a node situated at the same depth as ${y_2}$ and at distance ${a}$ from ${y_1}$. The colour=depth property implies that, as far as distances between images under ${f}$ are concerned, ${\{y_0,y_1,y'_2\}}$ behaves learly as ${\{y_0,y_1,y_2\}}$ does, i.e. ${f(\{y_0,y_1,y_2,y'_2\})}$ is a fork. Therefore ${d(f(y_2),f(y'_2))}$ is small, whereas ${d(y_2,y'_2)=2a}$.