1. Let Hd  denote the d-dimensional hypercube (of size n = 2d ).

(a) Prove that there exists a Ramsey embedding of Hd  (with e1 metric) into an equilateral metric space with distortion 1 + ∈, with core of size ≥ nΩ(e2 ) , for 0 < ∈ < 1.  Hint. Prove the existence of the embedding via the probabilistic argument, using Chernoff bound.

BONUS Prove that there exists a Ramsey embedding of Hd  into an equilateral metric space with distortion α > 1, with core of size ≥ n1-g(α), where g(α) → 0, when α → &.

2. Prove that for any finite metric space X there exists a probabilistic partition with padding parameter O(ddim(X)) (ddim(X) is a doubling dimension of X).  Directions: follow the proof of the Uniform Partition Lemma, replace each χj  with a fixed value χ such that log χ = Θ(ddim(X)). Explain the part of the proof that changed.

3.   (a) Describe a probabilistic embedding of an unweighted Cn into a distribution of k trees, with expected distortion O(n/k), for each 1 ≤ k ≤ n.

BONUS Extend the above statement for any weighted cycle on n points.

(b)  Show that for any probabilistic embedding of Cn  into a distribution of at most k

trees, the expected distortion is at least Ω(n/k).

4.   (a) Let G = (V, E) be a d-regular graph (where d is some fixed constant) on n vertices, with Cheeger constant δ(G), i.e.

δ(G) = ScV,1s(m)sn/2 {  } .

Prove that there exists a subset A ∈ V , |A| ≥ n1-O(1/α), such that (A, dG ) can be embedded into an equilateral metric space with distortion α > 1, where the big O hides the factor (log d)/ log(1 + δ(G)).

Directions:  bound the number of vertices within distance l from any given vertex, and bound the diameter of G (as functions of δ(G), d, and n).

(b)  Show that for any graph G = (V, E) on n vertices, for any embedding f : G → e1  it

holds that

|f (u) 一 f (v)|1  ≤                      |f (u) 一 f (v)|1

uveV                                                           e=(u,v)eE

Hint:  recall that any metric in e1  is a linear combination (with positive scalars) of cut metrics.