** The minimal distortion needed to embed a binary tree into **

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 participants as a complete graph some of whose edges are coloured. We want a triangle painted in one single colour.

The answer is .

** 1.2. Ramsey’s theorem **

Theorem 1 (Ramsey)Given , , there exists such that if , in any graph with vertices, there exists either an -clique (complete subgraph) or an -independent set (no edges between them).

We just saw that . It is known that .

\indent{*If aliens would threaten Earth of war unless we can give them the value of , we should put all our efforts to find it. If they would ask for , 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 -convex Banach spaces **

See Li’s lecture for the definition of -convexity. Hilbert space is 2-convex. is -convex if and 2-convex if .

Theorem 2Let be a -convex Banach space. Let be the complete rooted binary tree of depth . For any embedding ,

** 2.2. Hanner’s inequality **

If ,

If , the inequalities are reversed.

** 2.3. Forks **

A 4-tuple of points is a *-fork* if and are -isomorphic to (mapping to 1).

Lemma 3In a -convex Banach space, , every -fork satisfies

**Proof**. One can assume that , . Let

Then , . Apply -convexity inequality to unit vectors and . Their midpoint is , and . Therefore . Furthermore,

thus .

** 2.4. Combinatorics in rooted trees **

Let be a rooted tree. Let denote the set of pairs of vertices with on the path from the root to .

Denote by denote the complete -ary tree of depth .

Lemma 4Let . Colour in colours. Then there is a copy of such that the colour of any pair only depends on the levels of and .

We start with the following

**Claim**. It the leaves of are coloured by colours and , then there is a copy of inside with monochromatic leaves.

This is proven by induction on . Below the root, there are trees isomorphic to . By induction, in each of them, there is a binary subtree with monocoloured leaves. Since , two of these binary subtrees have the same leaf colour. Connect them via the root, this yields a binary subtree with monocoloured leaves.

**Back to the proof of the Lemma**. We label each leaf of by a vector whose components are the colours of the successive pairs along the path from to . So the number of labels is . According to the Claim, there is a binary subtree 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 5embeds into for .

Lemma 6 (Path embedding lemma)Given , , there exists such that every distance non decreasing mapin some metric space , with , , there exists an arithmetic progression

such that the restriction of to is -isometric, for .

Let be a distance non decreasing map, of distorsion . We shall look for forks in the image. We start with a complete -ary subtree of . We colour the elements of according to the distorsion of : the colour is the integer part of

a small constant.

Thanks to our Ramsey type Lemma, we find a complete binary subtree in with nodes coloured by their depth only. Along each path from root to a leaf, we find an arithmetic progression of step along which is nearly isometric. Let be a node situated at the same depth as and at distance from . The colour=depth property implies that, as far as distances between images under are concerned, behaves learly as does, i.e. is a fork. Therefore is small, whereas .