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<p<2}.

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}.

We start with the following

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}.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s