Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs

Assaf Naor^{∗}  Yuval Rabani^{†}  Alistair Sinclair^{‡}

Abstract It is shown that the edges of any n-point vertex expander can be replaced by new edges so that the resulting graph is an edge expander, and such that any two vertices that are joined by a new edge are at distance O(\sqrt{log n}) in the original graph. This result is optimal, and is shown to have various geometric consequences. In particular, it is used to obtain an alternative perspective on the recent algorithm of Arora, Rao and Vazirani [2] for approximating the edge expansion of a graph, and to give a nearly optimal lower bound on the ratio between the observable diameter and the diameter of doubling metric measure spaces which are quasisymmetrically embeddable in Hilbert space.

1 Introduction

Expansion properties of graphs are a fundamental tool in modern combinatorics. Questions related to expansion have found deep connections to numerous mathematical disciplines, such as number theory, Lie groups, measure theory, geometry and topology, mixing times of Markov chains, derandomization and coding theory. The various forms of graph expansion can be viewed as discrete analogs of isoperimetery, and are thus intimately related to classical analytic concepts.

From a computational point of view, the Sparsest Cut Problem, which involves calculating the edge expansion of a graph, is a well known NP-hard problem, and hence not solvable in polynomial time (unless P = NP). Whether it is possible to efficiently compute a good approximation to the edge expansion is arguably one of the most important outstanding questions in the field of approximation algorithms. A recent breakthrough in this direction, due to Arora, Rao and Vazirani [2], yields a polynomial time algorithm which computes the edge expansion of an n-vertex graph within a factor of O(\sqrt{log n}). (Previously the best known approximation guarantee had been O(log n) [11].)

The present paper builds on the remarkable ideas of [2] to obtain new structural information on the relation between edge expansion and vertex expansion, which is shown to have applications to the theory of quasisymmetric embeddings. Additionally, we highlight a new perspective on the results of [2] which we believe is at the core of the phenomenon discovered there. Specifically, we formulate a geometric fact which implies the main results of [2] without using negative type (also known as squared L_{2}) triangle inequality conditions (see below for a definition). While the negative type condition is natural from the point of view of semidefinite programming, we find it to be an unnatural geometric assumption. Although the proofs in [2] use this condition in an essential way, we show that the results of [2] are actually based on a purely Euclidean geometric fact.

∗Theory Group, Microsoft Research. One Microsoft Way, Redmond WA 98052-6399. Email:anaor@microsoft.com

†Computer Science Department, Technion — Israel Institute of Technology, Haifa 32000, Israel. Email:

rabani@cs.technion.ac.il. This work was done while the author was on sabbatical leave at Cornell University.

Part of this work was done while the author was visiting Microsoft Research, Redmond.

‡Computer Science Division, University of California, Berkeley CA 94720-1776, U.S.A. Email:

sinclair@cs.berkeley.edu. Supported in part by NSF ITR grant CCR-0121555. Part of this work was done while the author was on sabbatical leave at Microsoft Research, Redmond.

1.1 Vertex expansion, edge expansion, and the edge replacement theorem

We begin by recalling some classical definitions. In what follows all graphs are unweighted, and allowed to have multiple edges and self loops. We shall use the following notation. Given a graph G = (V, E) we denote by d_{G}(·, ·) the shortest path metric induced by G on V. For S ⊆ V, its neighborhood in G is defined as N_{G}(S) = {v ∈ V : d_{G}(v, S) = 1}. Given S, T ⊆ V, e(S, T) denotes the number of edges which intersect both S and T.

Definition 1.1 (Vertex expansion). Let G = (V, E) be a graph. Its vertex expansion h(G) is defined to be the largest constant h such that for every S ⊆ V with 1 ≤ |S| ≤ |V |/2 we have |N_{G}(S)| ≥ h|S|.

Definition 1.2 (Edge expansion). Let G = (V, E) be a graph. The edge expansion of G, denoted α(G), is the largest constant α such that for every S ⊆ V with 1 ≤ |S| ≤ |V |/2 we have

e(S, V \ S) ≥ α · \frac{|S| · |E|}{|V |}.

These two notions of expansion play a central role in modern combinatorics. It is clear that for a graph G = (V, E) of bounded average degree (i.e., |E| = O(|V |)), a lower bound on h(G) implies a lower bound on α(G). For graphs of unbounded average degree the same statement is clearly false in general. The main combinatorial result of this paper is the following:

Theorem 1.3 (Edge replacement theorem). There are absolute constants c, C > 0 with the following properties. For every n-vertex graph G = (V, E) with h(G) ≥ \frac{1}{2}, there is a set of edges E′ on V satisfying:

1. For every \{u, v\} ∈ E′, d_{G}(u, v) ≤ C\sqrt{log n}.

2. α(V, E′) ≥ c.

On the other hand, there are arbitrarily large n-vertex graphs G = (V, E) with h(G) ≥ \frac{1}{2} such that, for every c > 0 and every set of edges E′ on V for which α(V, E′) ≥ c, there is some {u, v} ∈ E′ satisfying d_{G}(u, v) ≥ \frac{c}{20} \sqrt{log n}.

Given a graph G = (V, E) and r ≥ 1, denote by G^{r} = (V, E^{r}) the graph whose edges are E^{r} = \{\{u, v\} : d_{G}(u, v) ≤ r\}. It is a standard fact that h (G^{⌈ \frac{2}{h(G)} ⌉}) ≥ \frac{1}{2}. Therefore, an immediate corollary of Theorem 1.3 is that the same result holds for arbitrary graphs, with the upper bound on the length of edges in E′ replaced by ⌈\frac{2C}{h(G)}⌉\sqrt{log n}.

The proof of Theorem 1.3 has two components: a geometric argument, presented in Section 3.2, which establishes the existence of a new edge set for which every large enough subset of the vertices has the appropriately large edge boundary, and a combinatorial argument, presented in Section 3.1, which takes care of the edge expansion of small subsets. The geometric component can be formally proved via a duality argument (presented in Section 3.1) using the main result of [2] as a “black box”; however, for the purposes of Theorem 1.3 it turns out that it is possible to use a simpler proof than that of [2], which is nevertheless strongly based on their ideas.

On the other hand, as we shall show in Section 2, Theorem 1.3 is easily seen to have powerful geometric consequences. Firstly, it actually readily implies the geometric fact from [2] (see also [10]) that lies at the heart of the approximation algorithm for sparsest cut given in [2]; we present this fact, and explain its algorithmic role, in the next subsection. Secondly, as we discuss in Section 1.3 below, it gives a nearly optimal lower bound on the observable diameter of doubling metric measure spaces which are quasisymmetrically equivalent to subsets of Hilbert space.

1.2 The relation to algorithmic graph partitioning

As stated above, the present paper is motivated by the recent algorithm of Arora, Rao and Vazirani [2] which, given an n-vertex graph G = (V, E), approximates in polynomial time its edge expansion up to a factor of O(\sqrt{log n}). In this subsection we explain how Theorem 1.3 leads to an alternative proof of the key geometric result of [2]; for the convenience of readers not familiar with [2], we also indicate how this result gives an approximation algorithm for edge expansion.

Let G be an n-vertex graph and define

β = min_{\begin{matrix}S⊆V \\ 1≤|S|≤n/2 \end{matrix}} \frac{e(S, V \ S)}{|S|}.

Take S ⊆ V with 1 ≤ |S| ≤ n/2 and e(S, V \ S) = β|S|. For every v ∈ V set x_{v} = 1 if v ∈ S and x_{v} = −1 otherwise. Then ∑_{u,v∈V} |x_{u} − x_{v}|^{2} = 4|S|(n − |S|) ≥ 2|S|n, and ∑_{{u,v}∈E} |x_{u} − x_{v}|^{2} = 4e(S, V \ S) = 4β|S|. Moreover, since x_{v} ∈ {−1, 1}, we have for every u, v, w ∈ V, |x_{v} − x_{u}|^{2} ≤ |x_{v} − x_{w}|^{2} + |x_{w} − x_{u}|^{2}. Hence, by normalization, if we let β^{∗} be the minimum of \frac{1}{n} ∑_{\{u,v\}∈E} ∥z_{u} − z_{v}∥_{2}^{2} over all choices of z_{1}, …, z_{n} ∈ S^{n−1} (the unit Euclidean sphere in ℝ^{n}) satisfying \frac{1}{n^{2}} ∑_{u,v∈V} ∥z_{u} − z_{v}∥_{2}^{2} = 1 and, for all u, v, w ∈ V, ∥z_{v} − z_{u}∥_{2}^{2} ≤ ∥z_{v} − z_{w}∥_{2}^{2} + ∥z_{w} − z_{u}∥_{2}^{2}, then β^{∗} ≤ 2β.

The advantage of passing to β^{∗} is that such a semidefinite minimization problem can be solved in polynomial time (up to an arbitrarily small additive error) using the ellipsoid algorithm (see, e.g., [8] for details on semidefinite programming). Hence, we can efficiently produce vectors z_{v} ∈ S^{n−1} satisfying the above constraints such that ∑_{{u,v}∈E} ∥z_{u} − z_{v}∥_{2}^{2} ≤ (1 + o(1))β^{∗}n. Now, as we shall see below, there exists a universal constant c > 0 such that

β^{∗} ≥ \frac{c}{\sqrt{log n}} · β.  (1)

Thus, it is possible to evaluate β within a factor of O(\sqrt{log n}) in polynomial time. This algorithm is one of the main results of [2].^{1}

Let z_{1}, ⋯, z_{n} be a set of vectors as above such that ∑_{{u,v}∈E} ∥z_{u} − z_{v}∥_{2}^{2} ≤ 2β^{∗}n, and for u, v ∈ V denote d(u, v) = ∥z_{u} − z_{v}∥_{2}^{2}. Our constraints imply that (V, d) is a metric space. (Such metrics are commonly known as metrics of negative type, or squared L_{2} metrics.) Let diam(V) = max_{u,v∈V} d(u, v) be the diameter of V. The key geometric fact from [2] that is used to deduce (1) is the following:

1In addition, [2] also gives an algorithm for finding a subset S ⊆ V that achieves the desired approximation.

Theorem 1.4. Let (V, d) be an n-point metric space of negative type with diameter 1. Assume that

\frac{1}{n^{2}} ∑_{u,v∈V} d(u, v) ≥ δ

for some δ > 0. Then there are A, B ⊆ V with |A|, |B| ≥ \frac{δ}{16}n and d(A, B) ≥ \frac{κ}{\sqrt{log n}}, where κ > 0 depends only on δ.

We will show in Section 2 how to deduce Theorem 1.4 fairly painlessly from Theorem 1.3; in fact, we will deduce much more general versions (Theorems 2.4 and 2.5) that apply to all metrics that are uniformly embeddable and all metrics that are quasisymmetrically embeddable in Hilbert space (see Section 1.3 below for definitions). Thus the property in Theorem 1.4 is quite general and not special to metrics of negative type.

For completeness, we now indicate how to derive (1) from Theorem 1.4; here we are essentially repeating the argument of [2]. Let B(v, r) denote the open ball of radius r centered at v, i.e., B(v, r) = {u ∈ V : d(u, v) < r}. Assume first that for every v ∈ V, |B(v, 1/8)| ≤ n/8. Since \frac{1}{n^{2}} ∑_{u,v∈V} d(u, v) = 1 there is some vertex w ∈ V for which |B(w, 2)| ≥ n/4. Moreover, by our assumption we have that

\frac{1}{|B(w, 2)|^{2}} ∑_{u,v∈B(w,2)} d(u, v) ≥ \frac{1}{|B(w, 2)|^{2}} ∑_{u∈B(w,2)} ∑_{v∈B(w,2)\B(u,1/8)} d(u, v)

≥ \frac{1}{|B(w, 2)|} · (|B(w, 2)| − \frac{n}{8}) ≥ \frac{1}{16}.

Hence, by Theorem 1.4 there are universal constants a, b ∈ (0, 1/2) and A, B ⊆ V with |A|, |B| ≥ an and d(A, B) > b/\sqrt{log n}.

For t ∈ [0, b/\sqrt{log n}] define S_{t} = \{v ∈ V : d(v, A) ≤ t\}. Then for all t, an ≤ |S_{t}| ≤ (1 − a)n. Moreover, by a simple computation, for every u, v ∈ V,

∫_{0}^{b/\sqrt{log n}} |1_{S_{t}}(u) − 1_{S_{t}}(v)|dt ≤ |d(u, A) − d(v, A)| ≤ d(u, v),

implying that

\frac{\sqrt{log n}}{b} ∫_{0}^{b/\sqrt{log n}} ( ∑_{\{u,v\}∈E} |1_{S_{t}}(u) − 1_{S_{t}}(v)|) dt ≤ \frac{\sqrt{log n}}{b} ∑_{\{u,v\}∈E} ∥z_{u} − z_{v}∥_{2}^{2} ≤ \frac{2\sqrt{log n}}{b} · β^{∗}n.

We deduce that there is some t ∈ [0, b/\sqrt{log n}] for which

∑_{\{u,v\}∈E} |1_{S_{t}}(u) − 1_{S_{t}}(v)| = e(S_{t}, V \ S_{t}) ≤ \frac{2\sqrt{log n}}{b} · β^{∗}n.

Since 1 ≤ |V \ S_{t}| ≤ n/2, e(S_{t}, V \ S_{t}) ≥ β|V \ S_{t}| ≥ βan. We conclude that β^{∗} ≥ \frac{ab}{2\sqrt{log n}} · β.

It remains to deal with the case in which there exists w ∈ V such that |B(w, 1/8)| > n/8. Since \frac{1}{n^{2}} ∑_{u,v∈V} d(u, v) = 1, and diam(V) = 1, there are at least n^{2}/2 pairs (u, v) ∈ V × V for which d(u, v) ≥ \frac{1}{2}. By the triangle inequality, for such pairs (u, v) we have max\{d(u, w), d(v, w)\} ≥ 1/4, so that |V \ B(w, 1/4)| ≥ n/2. Setting A = B(w, 1/8) and B = V \ B(w, 1/4), we have d(A, B) ≥ 1/8 and |A|, |B| ≥ n/8, so we are again in the situation of the above argument (in this case we actually get that β = O(β^{∗})).

1.3 Uniform and quasisymmetric embeddings and the observable diameter

A metric measure space is a triple (X, d, μ) consisting of a metric space (X, d) and a Borel probability measure μ on X. Let B(x, r) denote the open ball of radius r centered at x and, for A ⊆ X and ε > 0, define A_{ε} = {x ∈ X : d(x, A) < ε}. In what follows all subsets of metric spaces are assumed to be Borel measurable. The measure μ is said to be doubling with constant λ if for every x ∈ X and r > 0, μ(B(x, 2r)) ≤ λμ(B(x, r)). The isoperimetric function of μ is defined as:

I_{μ}^{(X,d)}(ε) = sup \{μ(X \ A_{ε}) : μ(A) ≥ \frac{1}{2}\} .

Following M. Gromov (see [7] and the references therein) we recall the notion of observable diameter of a metric measure space: the observable diameter of (X, d, μ) with parameter κ > 0, denoted Obs_{μ}(X, d; κ), is defined by

Obs_{μ}(X, d; κ) = sup{ε > 0 : I_{μ}^{(X,d)}(ε) ≥ κ}.

The motivation for this nomenclature is as follows. Assume that we are trying to “measure” the size of (X, d, μ). We make observations which consist of real valued 1-Lipschitz functions on X, i.e. we assign to each point of X a real number in a Lipschitz smooth way. We plot the distribution of these observations, and account for possible observational errors by discarding the part of the distribution which does not belong to a symmetric interval around its median of mass at least 1−κ. The length of this “central” interval will never exceed Obs_{μ}(X, d; κ).

Let S^{d−1} ⊆ ℝ^{d} be the unit Euclidean sphere, equipped with the standard Euclidean metric, and let σ be the normalized surface area measure on S^{d−1}. Levy’s isoperimetric inequality (see, e.g., [13]) states that for every 0 < ε < π/2, I_{σ}^{(S^{d−1},∥·∥_{2})}(ε) ≤ \sqrt{\frac{π}{8}} e^{−dε^{2}/2}. It follows that for every κ ≤ 1,

Obs_{σ}(S^{d−1}, ∥ · ∥_{2}; κ) = O (\sqrt{\frac{log(2/κ)}{d}}) ,

while the diameter of S^{d−1} equals 2. Spaces for which the observable diameter is much smaller than the diameter are sometimes (following V. Milman) said to have “small isoperimetric constant.”

In order to state our main geometric result we require the following classical definitions:

Definition 1.5 (Uniform embedding). Let (X, d_{X}), (Y, d_{Y}) be metric spaces and α, β : [0, ∞) → [0, ∞) be strictly increasing functions. A one to one mapping f : X ↪ Y is called a uniform embedding with moduli α and β if for every x, y ∈ X,

α(d_{X}(x, y)) ≤ d_{Y} (f(x), f(y)) ≤ β(d_{X}(x, y)).

When the moduli α and β are of the form α(t) = Ct and β(t) = C · L · t we say that the embedding f is L-bi-Lipschitz.

We now recall the important notion of quasisymmetric embeddings, which was first introduced by Beurling and Ahlfors in [4].

Definition 1.6 (Quasisymmetric embedding). Let (X, d_{X}), (Y, d_{Y}) be metric spaces and η : [0, ∞) → [0, ∞) a strictly increasing function. A one to one mapping f : X ↪ Y is called a quasisymmetric embedding with modulus η if for every x, a, b ∈ X such that x ≠ b,

\frac{d_{Y} (f(x), f(a))}{d_{Y} (f(x), f(b))} ≤ η (\frac{d_{X}(x, a)}{d_{X}(x, b)}) .

Uniform and quasisymmetric embeddings are central notions in modern geometric analysis (see [7, 9, 14]). Roughly speaking, bi-Lipschitz embeddings preserve distances, while quasisymmetric embeddings preserve “thickness of triangles”, and hence, in a sense, preserve shape (quasisymmetric embeddings are a natural metric analog of quasiconformal mappings). As an example, consider the classical isometric embedding of L_{1}, equipped with the metric \sqrt{∥x − y∥_{1}}, into L_{2}. The image of such an embedding consists of a set X ⊆ L_{2} on which the function ∥x−y∥_{2}^{2} is a metric. (These are just the metrics of negative type as defined in the previous subsection.) This embedding is both uniform (with α(t) = β(t) = \sqrt{t}) and quasisymmetric (in fact, any uniform embedding with moduli α(t), β(t) = Θ(t^{a}) is clearly a quasisymmetric embedding). Additional examples, showing that the notions of uniform and quasisymmetric embeddings are incomparable, can be found in [9].

Although we formulate our results both for uniform and quasisymmetric embeddings, quasisymmetric embeddings are more natural to work with in the context of studying isoperimetric functions. The significance of the metrics of negative type in [2] stems from the fact that they quasisymmetrically embed in Hilbert space; see Section 2 for more details on this point.

The following result is deduced from Theorem 1.3 in Section 2. It states that (up to double logarithmic factors) any non-degenerate metric measure space which is doubling with constant λ and is quasisymmetrically equivalent to a subset of Hilbert space cannot have an observable diameter which is smaller than the observable diameter of the Euclidean sphere of dimension O(log λ).

Theorem 1.7. Let (X, d) be a bounded metric space and μ a Borel probability measure on X which is doubling with constant λ > 3, i.e., for every x ∈ X and r > 0, μ(B(x, 2r)) ≤ λμ(B(x, r). Assume that

∫_{X×X} d(x, y)dμ(x)dμ(y) ≥ δ diam(X)  (2)

for some δ > 0. Let f : X → ℓ_{2} be a quasisymmetric embedding with modulus η. Then

\frac{Obs_{μ}(X, d; κ)}{diam(X)} ≥ \frac{τ}{\sqrt{(log λ)(log log λ)}}

where κ = κ(δ, η) and τ = τ(δ, η) depend only on δ and η.

There is a natural analog of Theorem 1.7 in the case of uniform embeddings (see the remarks at the end of Section 2). However, in this case we need some restriction on the diameter of X, since it is typically impossible to scale a uniform embedding without changing its moduli (unless, of course, the moduli α and β are both homogeneous of the same order).

2 The geometric consequences of Theorem 1.3

We begin with the following well known fact, which relates edge expansion to certain Poincaré inequalities.

Fact 2.1. Let G = (V, E) be a graph. Then for every function f : V → L_{1},

\frac{1}{|E|} ∑_{\begin{matrix}u,v∈V \\ \{u,v\}∈E \end{matrix}} ∥f(u) − f(v)∥_{1} ≥ \frac{α(G)}{|V |^{2}} ∑_{u,v∈V} ∥f(u) − f(v)∥_{1}.

Proof. We include the standard proof for the sake of completeness. Note that for every S ⊆ V,

\frac{1}{|E|} ∑_{\begin{matrix}u,v∈V \\ \{u,v\}∈E \end{matrix}} |1_{S}(u) − 1_{S}(v)| = \frac{2e(S, V \ S)}{|E|}

≥ 2α(G) · \frac{|S|(|V | − |S|)}{|V |^{2}}
= \frac{α(G)}{|V |^{2}} ∑_{u,v∈V} |1_{S}(u) − 1_{S}(v)|.

Fix f : V → L_{1}. By the the cut-cone representation of the L_{1} metric f(V) [5], for every S ⊆ V there is t_{S} ≥ 0 such that for every u, v ∈ V,

∥f(u) − f(v)∥_{1} = ∑_{S⊆V} t_{S}|1_{S}(u) − 1_{S}(v)|.

Hence

\frac{1}{|E|} ∑_{\begin{matrix}u,v∈V \\ \{u,v\}∈E \end{matrix}} ∥f(u) − f(v)∥_{1} = ∑_{S⊆V} t_{S} \frac{1}{|E|} ∑_{\{u,v\}∈E} |1_{S}(u) − 1_{S}(v)|

≥ ∑_{S⊆V} t_{S} \frac{α(G)}{|V |^{2}} ∑_{u,v∈V} |1_{S}(u) − 1_{S}(v)|

= \frac{α(G)}{|V |^{2}} ∑_{u,v∈V} ∥f(u) − f(v)∥_{1}.

We are now in position to prove the second assertion in Theorem 1.3, i.e., the fact that the result is existentially optimal. Fix an integer d ≥ 1 and consider the discrete cube V = {0, 1}^{d}, equipped with the Hamming metric ρ(x, y) = |{i : x_{i} ≠ y_{i}}|. The vertex isoperimetric inequality for the counting measure on V (see [1]) implies that for every S ⊆ V with 1 ≤ |S| ≤ 2^{d−1}, |\{x ∈ V : 0 < ρ(x, S) ≤ 10\sqrt{d}\}| ≥ \frac{|S|}{2}. It follows that if we define a graph G = (V, E) by E = \{\{u, v\} ⊆ \binom{V}{2} : ρ(u, v) ∈ [1, 10\sqrt{d}]\} then h(G) ≥ \frac{1}{2}. Let E′ be a set of edges on V for which

α(V, E′) ≥ c. By Fact 2.1 applied to the identity mapping from V into ℓ_{1}^{d} we get that

\frac{1}{|E′|} ∑_{\begin{matrix}u,v∈V \\ \{u,v\}∈E′ \end{matrix}} ρ(u, v) ≥ \frac{c}{|V |^{2}} ∑_{u,v∈V} ρ(u, v) = \frac{c}{2^{d}} ∑_{k=0}^{d} k\binom{d}{k} = \frac{cd}{2}.

It follows that there is an edge \{u, v\} ∈ E′ with ρ(u, v) ≥ \frac{cd}{2}. Since ρ(u, v) ≤ 10\sqrt{d} · d_{G}(u, v) we deduce that d_{G}(u, v) ≥ \frac{c}{2} \sqrt{d} ≥ \frac{c}{20} \sqrt{log |V |}, as required.

The following result is an immediate consequence of Theorem 1.3 and Fact 2.1 (using the fact that ℓ_{2} is isometric to a subset of ℓ_{1}):

Corollary 2.2. Let G = (V, E) be an n-vertex graph with h(G) ≥ \frac{1}{2}. Assume that f : V → ℓ_{2} satisfies

\frac{1}{n^{2}} ∑_{u,v∈V} ∥f(u) − f(v)∥_{2} ≥ δ.

Then there are u, v ∈ V with d_{G}(u, v) ≤ C\sqrt{log n} such that ∥f(u) − f(v)∥_{2} ≥ cδ. Here C, c are as in Theorem 1.3.

In order to deduce various geometric results from Corollary 2.2 we require the following simple combinatorial fact. Here, and in what follows, given a graph G = (V, E) and a subset of the vertices U ⊆ V, we denote the graph induced by G on U by G[U], i.e., G[U] = (U, E ∩ \binom{U}{2}).

Lemma 2.3. Fix 0 < ε ≤ \frac{1}{10} and let G = (V, E) be a graph such that for every X, Y ⊆ V satisfying |X|, |Y | ≥ ε|V |, d_{G}(X, Y) ≤ 1. Then there is U ⊆ V with |U| ≥ (1 − ε)|V | such that h(G[U]) ≥ \frac{1}{2}.

Proof. Construct graphs G = G_{0}, G_{1} = (V_{1}, E_{1}), …, G_{k} = (V_{k}, E_{k}) as follows. If there exists a set W_{i} ⊆ V_{i} such that |W_{i}| ≤ \frac{1}{2}|V_{i}| and |N_{G_{i}}(W_{i})| ≤ \frac{1}{2}|W_{i}|, put G_{i+1} = G_{i}[V_{i} \ W_{i}]. By construction, when this process terminates h(G_{k}) ≥ \frac{1}{2}. Define W = ⋃_{i=0}^{k−1} W_{i}.

If |W | ≤ ε|V | we are done. Otherwise let j be the minimal integer such that |W_{1}| + … + |W_{j}| > ε|V |. For X = ⋃_{i=1}^{j} W_{i} we have that d_{G}(X, V \ [X ⋃ N_{G}(X)]) > 1. By our assumption it follows that |V | − |X| − |N_{G}(X)| < ε|V |, or |N_{G}(X)| > (1 − ε)|V | − |X|. But

(1 − ε)|V | − |X| ≤ |N_{G}(X)| ≤ ∑_{i=0}^{k−1} |N_{G_{i}}(W_{i})| < ∑_{i=0}^{k−1} \frac{1}{2}|W_{i}| = \frac{1}{2}|W |,

or |X| > \frac{2(1−ε)}{3}|V |. By the minimality of j, |W_{1}| + … + |W_{j−1}| ≤ ε|V |, so that

\frac{|V |}{2} ≥ |W_{j}| ≥ |X| − ε|V | > \frac{2(1 − ε)}{3}|V | − ε|V |.

It follows that \frac{1}{2} > \frac{2(1−ε)}{3} − ε, contradicting the fact that ε ≤ \frac{1}{10}.

We now prove a generalization of Theorem 1.4, which was stated for negative type metrics in Section 1.2. The generalization applies to all metrics that uniformly embed into ℓ_{2}. We show that every such metric has two large subsets that are far apart. The main idea of the proof is that if every pair of sufficiently large subsets are close, then the graph connecting pairs of close points contains a large vertex expander (by Lemma 2.3), but then the embedded edge expander constructed by the edge replacement theorem (Theorem 1.3) violates the Poincaré inequality proved in Fact 2.1. Since negative type metrics embed uniformly with moduli α(t) = β(t) = \sqrt{t}, readers who are chiefly interested in the application to sparsest cut may simplify the proof below by specializing to this case.

Theorem 2.4. Let (X, d) be an n-point metric space with diameter 1. Fix δ > 0 and a uniform embedding f : X → ℓ_{2} with moduli α and β. Assume that

\frac{1}{n^{2}} ∑_{x,y∈X} d(x, y) ≥ δ.

Then there are A, B ⊆ X with |A|, |B| ≥ \frac{δ}{16}n and d(A, B) ≥ \frac{κ}{\sqrt{log n}}, where κ = κ(δ, α, β) depends only on δ, α and β.

Proof. Let c, C be as in Corollary 2.2. We will show that κ = \frac{1}{C} β^{−1} (\frac{cδα(δ/2)}{4}) works. Assume the contrary. By translation, without loss of generality f(X) ⊆ β(1)B^{n}, where B^{n} is the unit Euclidean ball in ℝ^{n}. Define a graph G = (X, E) by setting

E = \{\{x, y\} ⊆ \binom{X}{2} : d(x, y) < β^{−1} (\frac{cδα(δ/2)}{4}) · \frac{1}{C\sqrt{log n}}\} .

By the contrapositive assumption for every A, B ⊆ X with |A|, |B| ≥ \frac{δ}{16}n, d_{G}(A, B) ≤ 1. By Lemma 2.3 there is a subset X′ ⊆ X with |X′| ≥ (1 − δ/16)n such that h(G[X′]) ≥ \frac{1}{2}. Denoting D = \{(x, y) ∈ X × X : d(x, y) ≥ \frac{δ}{2}\} we have that |D| ≥ \frac{δ}{2}n^{2}. It follows that |D ∩ (X′ × X′)| ≥ \frac{δ}{4}n^{2}. So,

\frac{1}{|X′|^{2}} ∑_{x,y∈X′} ∥f(x) − f(y)∥_{2} ≥ \frac{1}{n^{2}} |D ∩ (X′ × X′)|α(δ/2) ≥ \frac{δα(δ/2)}{4}.

By Corollary 2.2 there are x, y ∈ X′ such that ∥f(x)−f(y)∥_{2} ≥ \frac{cδα(δ/2)}{4}, and d_{G}(x, y) ≤ C\sqrt{log n}. It follows that there is k ≤ C\sqrt{log n} and \{x = x_{0}, x_{1}, …, x_{k−1}, x_{k} = y\} ⊆ X such that for all i ≥ 1, d(x_{i}, x_{i−1}) < β^{−1} (\frac{cδα(δ/2)}{4}) · \frac{1}{C\sqrt{log n}}. But,

β^{−1} (\frac{cδα(δ/2)}{4}) ≤ d(x, y) ≤ ∑_{i=1}^{k} d(x_{i}, x_{i−1}) < C\sqrt{log n} · β^{−1} (\frac{cδα(δ/2)}{4}) · \frac{1}{C\sqrt{log n}},

a contradiction.

Remark 2.1. We note the assumption of unit diameter in Theorem 2.4. It is easy to see that the proof generalizes to the case of arbitrary diameter, but then the constant κ would depend nontrivially on diam(X). This is a manifestation of the fact that uniform embeddings do not in general scale well, and is also the reason we focus mainly on quasisymmetric embeddings (see below). For the specific application to the sparsest cut algorithm in [2], Theorem 2.4 is sufficient because the argument makes use only of ratios between distances, and thus is scale-free (see Section 1.2).

We now present an analog of Theorem 2.4 which applies to any metric that is quasisymmetrically embeddable in ℓ_{2}. As discussed in the remark above, this version has the advantage of being “scalefree” (in the sense that the result holds uniformly in the diameter).

Theorem 2.5. Let (X, d) be an n-point metric space and f : X → ℓ_{2} a quasisymmetric embedding with modulus η. Assume that

\frac{1}{n^{2}} ∑_{x,y∈X} d(x, y) ≥ δ diam(X)

for some δ > 0. Then there are A, B ⊆ X with |A|, |B| ≥ \frac{δ}{16}n and d(A, B) ≥ \frac{γ diam(X)}{\sqrt{log n}}, where γ = γ(δ, η) depends only on δ and η.

Proof. The proof is similar to the proof of Theorem 2.4. For c, C as in Corollary 2.2 denote

γ = \frac{η^{−1} (\frac{cδ}{8η(2/δ)+4})}{η^{−1} (\frac{cδ}{8η(2/δ)+4}) + 2} · \frac{1}{C} ,

and define a graph G = (X, E) by setting E = \{\{x, y\} ⊆ \binom{X}{2} : d(x, y) < γ diam(X)/\sqrt{log n}\}. We assume for the sake of contradiction that there are no A, B ⊆ X with d(A, B) ≥ γ diam(X)/\sqrt{log n} and |A|, |B| ≥ \frac{δn}{16}, i.e., for all A, B of this size we have d_{G}(A, B) ≤ 1. By Lemma 2.3 there is a subset X′ ⊆ X with |X′| ≥ (1 − δ/16)n such that h(G[X′]) ≥ \frac{1}{2}. Denoting D = \{(x, y) ∈ X × X : d(x, y) ≥ \frac{δ}{2} diam(X)\} we have that |D| ≥ \frac{δ}{2}n^{2}. It follows that |D ∩ (X′ × X′)| ≥ \frac{δ}{4}n^{2}.

Fix (x_{0}, y_{0}) ∈ D ∩ (X′ × X′) and x, y ∈ X. Since d(x_{0}, x) ≤ diam(X) ≤ \frac{2}{δ}d(x_{0}, y_{0}) we have that ∥f(x_{0}) − f(x)∥_{2} ≤ η(2/δ)∥f(x_{0}) − f(y_{0})∥_{2}. Similarly, ∥f(y_{0}) − f(y)∥_{2} ≤ η(2/δ)∥f(x_{0}) − f(y_{0})∥_{2}, so ∥f(x) − f(y)∥_{2} ≤ [2η(2/δ) + 1] · ∥f(x_{0}) − f(y_{0})∥_{2}. This shows that ∥f(x_{0}) − f(y_{0})∥_{2} ≥ \frac{diam(f(X))}{2η(2/δ)+1} whenever (x_{0}, y_{0}) ∈ D ∩ (X′ × X′). Hence

\frac{1}{|X′|^{2}} ∑_{x,y∈X′} ∥f(x) − f(y)∥_{2} ≥ \frac{|D ∩ (X′ × X′)|}{n^{2}} · \frac{diam(f(X))}{2η(2/δ) + 1} ≥ \frac{δ}{8η(2/δ) + 4} · diam(f(X)).

By Corollary 2.2 there are x, y ∈ X′ such that ∥f(x) − f(y)∥_{2} ≥ \frac{cδ}{8η(2/δ)+4} · diam(f(X)), and d_{G}(x, y) ≤ C\sqrt{log n}. It follows that there is k ≤ C\sqrt{log n} and \{x = x_{0}, x_{1}, …, x_{k−1}, x_{k} = y\} ⊆ X such that for all i ≥ 1, d(x_{i}, x_{i−1}) < γ diam(X)/\sqrt{log n}. Consider now an arbitrary pair x′, y′ ∈ X. We have ∥f(x) − f(x′)∥_{2} ≤ diam(f(X)) ≤ \frac{8η(2/δ)+4}{cδ}∥f(x) − f(y)∥_{2}, so since f is a quasisymmetry with modulus η,

η (\frac{d(x, y)}{d(x′, x)}) ≥ \frac{∥f(x) − f(y)∥_{2}}{∥f(x′) − f(x)∥_{2}} ≥ \frac{cδ}{8η(2/δ) + 4},

or d(x′, x) ≤ _{\frac{d(x,y)}{η^{−1}( \frac{cδ}{8η(2/δ)+4} )}}. Similarly d(y′, y) can be bounded by the same quantity, so that

d(x′, y′) ≤ [\frac{2}{η^{−1} (\frac{cδ}{8η(2/δ)+4})} + 1] d(x, y).

Since this is true for all x′, y′ ∈ X,

d(x, y) ≥ \frac{η^{−1} (\frac{cδ}{8η(2/δ)+4})}{η^{−1} (\frac{cδ}{8η(2/δ)+4}) + 2} · diam(X) = Cγ · diam(X).

But

Cγ · diam(X) ≤ d(x, y) ≤ ∑_{i=1}^{k} d(x_{i}, x_{i−1}) < C\sqrt{log n} · γ diam(X)/\sqrt{log n},

a contradiction.

Corollary 2.6. Let (X, d) be a finite metric space and N, δ > 0. Assume that μ is a probability measure on X such that for every x ∈ X, μ(x) ≥ \frac{1}{N} and ∫_{X×X} d(x, y)dμ(x)dμ(y) ≥ δ diam(X). Let f : X → ℓ_{2} be a quasisymmetric embedding with modulus η. Then there are A, B ⊆ X with μ(A), μ(B) ≥ \frac{δ}{16} and d(A, B) ≥ \frac{γ̃ diam(X)}{\sqrt{log N}}, where γ̃ = γ̃(δ, η) depends only on δ and η.

Figure 1: The net N and the partition {T_{1}, …, T_{n}}.

Proof. The proof is a simple duplication of points argument. Without loss of generality assume that μ(x) is rational for all x ∈ X, and write μ(x) = \frac{m_{x}}{M}, where ∑_{x∈X} m_{x} = M; by our assumption on μ, M = O(N). For every x ∈ X let {x(i)}_{i=1}^{m_{x}} be copies of x, and consider the semi-metric space X̃ = ⋃_{x∈X}{x(i)}_{i=1}^{m_{x}}, where dX̃(x(i), y(j)) = d_{X}(x, y) if x ≠ y and dX̃(x(i), x(j)) = 0. Clearly |X̃| = M = O(N) and \frac{1}{M^{2}} ∑_{a,b∈X̃} dX̃(a, b) ≥ δ diam(X̃). By Theorem 2.5 there are Ã, B̃ ⊆ X̃ with

|Ã|, |B̃| ≥ \frac{δM}{16} and dX̃(Ã, B̃) = Ω_{δ,η} (\frac{diam(X̃)}{\sqrt{log M}}) = Ω_{δ,η} (\frac{diam(X)}{\sqrt{log N}}). (One has to observe here that the proof of Theorem 2.5 works for semi-metrics as well, i.e., the condition d(x, y) > 0 for x ≠ y was never used.) Denote A = {x ∈ X : ∃i, x(i) ∈ Ã} and B = {x ∈ X : ∃i, x(i) ∈ B̃}. Then d(A, B) = Ω_{δ,η} (\frac{diam(X)}{\sqrt{log N}}). Additionally μ(A) = ∑_{x∈A} \frac{m_{x}}{M} ≥ \frac{1}{M} ∑_{x∈A} |\{1 ≤ i ≤ m_{x} : x(i) ∈ Ã\}| =

\frac{|Ã|}{M} ≥ \frac{δ}{16}, and similarly μ(B) ≥ \frac{δ}{16}, as required.

We are now in position to prove Theorem 1.7 which was stated in the introduction.

Proof of Theorem 1.7. Let k be a (large) integer which will be determined later; for now assume that 2^{−k} ≤ \frac{δ}{4}. Recall that a subset S ⊆ X is called ε-separated if for every distinct x, y ∈ S, d(x, y) ≥ ε. Let N be a maximal 2^{−k} diam(X) separated set in X. Since the balls {B(x, 2^{−k−1} diam(X))}_{x∈N} are disjoint and for every x ∈ X the doubling condition implies that μ(B(x, 2^{−k−1} diam(X))) ≥ λ^{−k−1}μ(B(x, diam(X)) = λ^{−k−1}, we have |N | ≡ n ≤ λ^{k+1}. Write N = {x_{1}, …, x_{n}}, and define inductively T_{1} = {x ∈ X : d(x, x_{1}) = d(x, N)}, T_{i+1} = {x ∈ X : d(x, x_{i}) = d(x, N)} \ ⋃_{j=1}^{i} T_{j}. Then {T_{1}, …, T_{n}} is a partition of X (which is described schematically in Figure 1), and for every x ∈ T_{i}, d(x, x_{i}) ≤ 2^{−k} diam(X).

Define a probability measure ν on N by ν(x_{i}) = μ(T_{i}). Since T_{i} ⊇ B(x_{i}, 2^{−k−1} diam(X)), we have that ν(x_{i}) ≥ λ^{−k−1}. Observe that

δ diam(X) ≤ ∫_{X×X} d(x, y)dμ(x)dμ(y)
= ∑_{i=1}^{n} ∑_{j=1}^{n} ∫_{T_{i}×T_{j}} d(x, y)dμ(x)dμ(y)

≤ ∑_{i=1}^{n} ∑_{j=1}^{n} ∫_{T_{i}×T_{j}}[d(x, x_{i}) + d(x_{i}, x_{j}) + d(x_{j}, y)]dμ(x)dμ(y)

≤ ∑_{i=1}^{n} ∑_{j=1}^{n} ∫_{T_{i}×T_{j}}[d(x_{i}, x_{j}) + 2^{−k+1} diam(X)]dμ(x)dμ(y)

= ∑_{i=1}^{n} ∑_{j=1}^{n} d(x_{i}, x_{j})ν(x_{i})ν(x_{j}) + 2^{−k+1} diam(X).

Since we assume that 2^{−k} ≤ \frac{δ}{4}, this implies ∫_{N ×N} d(x, y)dν(x)dν(y) ≥ \frac{δ}{2} diam(N). Hence by Corollary 2.6 there are A, B ⊆ N with ν(A), ν(B) ≥ \frac{δ}{32} and d(A, B) ≥ \frac{c diam(N)}{\sqrt{k log λ}}, where c is a constant depending on η and δ. Define A′ = ⋃_{x_{i}∈A} T_{i} and B′ = ⋃_{x_{i}∈B} T_{i}. Then μ(A′) = ν(A) ≥ \frac{δ}{32} and μ(B′) = ν(B) ≥ \frac{δ}{32}. Observe that since N is a 2^{−k} diam(X) net in X, diam(N) ≥ (1 − 2^{−k+1}) diam(X). Fix a ∈ A′ and b ∈ B′. There are x_{i} ∈ A and x_{j} ∈ B such that d(x_{i}, a) ≤ 2^{−k} diam(X) and d(x_{j}, b) ≤ 2^{−k} diam(X). Hence,

d(a, b) ≥ d(x_{i}, x_{j}) − d(x_{i}, a) − d(x_{j}, b) ≥ \frac{c(1 − 2^{−k+1}) diam(X)}{\sqrt{k log λ}} − 2^{−k+1} diam(X).

So, for k ≈ log log λ we get that

d(A′, B′) > \frac{c′ diam(X)}{\sqrt{(log λ)(log log λ)}},

where c′ is a constant depending only on η and δ.

Denote ζ = (I_{μ})^{−1}(μ(A′)/2). We claim that μ(A′_{ζ}) ≥ \frac{1}{2}. Indeed otherwise, the fact that (X \ A′_{ζ})_{ζ} ∩ A′ = ∅ implies that

1 − μ(A′) ≥ μ((X \ A′_{ζ})_{ζ}) ≥ 1 − I_{μ}(ζ) = 1 − \frac{μ(A′)}{2},

which is a contradiction. Denote ε = \frac{c′ diam(X)}{\sqrt{(log λ)(log log λ)}}. If ε ≥ 2ζ then since (A′_{ζ})_{ε/2} ⊆ A_{ε} we have

that μ(X \ A′_{ε}) ≤ I_{μ}(ε/2). But B′ ⊆ X \ A′_{ε}, so that I_{μ}(ε/2) ≥ μ(B′) ≥ \frac{δ}{32}. On the other hand, if ε < 2δ then

\frac{δ}{32} ≤ μ(B′) ≤ μ(X \ A′_{ε}) ≤ 1 ≤ \frac{I_{μ}(ε/2)}{I_{μ}(ζ)} = \frac{I_{μ}(ε/2)}{μ(A′)/2} ≤ \frac{64I_{μ}(ε/2)}{δ}.

In both cases we obtain the lower bound I_{μ}(ε/2) ≥ \frac{δ^{2}}{2500}.

Remark 2.2. A statement analogous to Theorem 1.7 in the case of uniform embeddings can be proved along the same lines using Theorem 2.4. In this case, the implicit constants must also depend on diam(X), since uniform embeddings do not scale well. This is why we preferred to deal with quasisymmetric embeddings — we feel that mappings which preserve shape are more naturally compatible with isoperimetric problems.

Remark 2.3. Consider the discrete cube X = {0, 1}^{d}, equipped with the Hamming metric ρ(x, y) = |\{i : x_{i} ≠ y_{i}\}|. Since (X, \sqrt{ρ}) is isometric to a subset of ℓ_{2}, it is also quasisymmetrically equivalent to a subset of ℓ_{2} (with modulus η(s) = \sqrt{s}). The concentration inequality for the uniform measure on X shows that Theorem 2.5 is optimal.

Remark 2.4. We do not know whether Theorem 2.5 is optimal when restricted to subsets of Hilbert space (i.e., the case η(s) = s). We can, however, show that it is optimal up to a double logarithmic term. Indeed, by Lemma 21 in [6] there is a constant c such that for every 1 < γ < π/2 there are disjoint subsets S_{1}, …, S_{N} ⊆ S^{d−1} of equal surface area, diameter at most γ and N ≤ (c/γ)^{d}. For each i = 1, …, N pick an arbitrary point x_{i} ∈ S_{i}. Assume that A, B ⊆ {x_{1}, …, x_{N}} satisfy |A|, |B| ≥ δN. Then, denoting A′ = ⋃_{x_{i}∈A} S_{i} and B′ = ⋃_{x_{i}∈B} S_{i}, we have that σ(A′), σ(B′) ≥ δ (here σ is the normalized surface area measure on S^{d−1}, and we have used the fact that all of the

S_{i} have the same surface area). By the concentration inequality for σ, d(A′, B′) = O (\sqrt{\frac{log(2/δ)}{d}}).

Since each of the sets S_{i} has diameter at most γ, we deduce that d(A, B) ≤ O (\sqrt{\frac{log(2/δ)}{d}}) + 2γ.

Choosing γ ≈ \sqrt{\frac{log(2/δ)}{d}} we get that N ≤ [c(δ)d]^{d}, implying that d(A, B) = O_{δ} (\sqrt{\frac{log log N}{log N}} ).

Theorem 2.5 implies that certain spaces do not quasisymetrically embed into Hilbert space, namely spaces for which the observable diameter is much smaller than the diameter. Examples of such spaces are bounded degree expanders, i.e., regular graphs of bounded degree whose edge expansion is large. However, in this particular case it is easy to deduce an even stronger restriction on their quasisymmetric embeddability into L_{p}, 1 ≤ p < ∞:

Proposition 2.7. Let G = (V, E) be an n-vertex d-regular graph. Fix 1 ≤ p < ∞ and assume that f : V → L_{p} is a quasisymmetric embedding with modulus η. Then

η (\frac{1}{log_{d}(n/4)}) ≥ \frac{α(G)}{4p}.

Proof. In [12] (see also [3]) it is shown that for every f : V → ℓ_{p},

\frac{1}{n^{2}} ∑_{u,v∈V} ∥f(u) − f(v)∥_{p}^{p} ≤ (\frac{2p}{α})^{p} \frac{1}{|E|} ∑_{\begin{matrix}u,v∈V \\ \{u,v\}∈E \end{matrix}} ∥f(u) − f(v)∥_{p}^{p}.  (3)

Since the number of vertices at distance at most t from a fixed vertex u ∈ V is at most 1 + d + d^{2} + ⋯ + d^{t} ≤ 2d^{t}, it follows that for every u ∈ V, |{v ∈ V : d_{G}(u, v) ≥ log_{d}(n/4)}| ≥ n/2.

Now

\frac{1}{n^{2}} ∑_{u,v∈V} ∥f(u) − f(v)∥_{p}^{p} = \frac{1}{dn^{2}} ∑_{\begin{matrix}u,v∈V \\ w∈N_{G}(u) \end{matrix}} ∥f(u) − f(v)∥_{p}^{p}

≥ \frac{1}{dn^{2}} ∑_{\begin{matrix}u,v∈V \\ w∈N_{G}(u) \end{matrix}} \frac{∥f(w) − f(u)∥_{p}^{p}}{[η(1/d_{G}(u, v))]^{p}}

≥ \frac{1}{dn^{2}} ∑_{\begin{matrix}u∈V \\ w∈N_{G}(u) \end{matrix}} \frac{∥f(w) − f(u)∥_{p}^{p}}{[η(1/ log_{d}(n/4))]^{p}} · |\{v ∈ V : d_{G}(u, v) ≥ log_{d}(n/4)\}|

≥ \frac{1}{2dn[η(1/ log_{d}(n/4))]^{p}} · 2 ∑_{\begin{matrix}u,w∈V \\ \{u,w\}∈E \end{matrix}} ∥f(u) − f(w)∥_{p}^{p}

= \frac{1}{2[η(1/ log_{d}(n/4))]^{p}} · \frac{1}{|E|} ∑_{\begin{matrix}u,w∈V \\ \{u,w\}∈E \end{matrix}} ∥f(u) − f(w)∥_{p}^{p}.

This lower bound, combined with (3), implies the required result.

3 Proof of Theorem 1.3

In Section 3.2 we show how the geometric ideas of [2] can be used to obtain the following statement, which is weaker than Corollary 2.2: For every δ > 0 there are constants c(δ), C(δ) > 0 such that, if G = (V, E) is an n-vertex graph satisfying h(G) ≥ \frac{1}{2} and f : V → ℓ_{2} is a Hilbert space valued function for which \frac{1}{n^{2}} ∑_{u,v∈V} ∥f(u) − f(v)∥_{2} ≥ δ, then there are u, v ∈ V with d_{G}(u, v) ≤ C(δ)\sqrt{log n} and ∥f(u) − f(v)∥_{2} ≥ c(δ). The same statement with C(δ) uniformly bounded in δ and c(δ) proportional to δ would suffice to prove Theorem 1.3. Unfortunately, we are unable to prove this fact directly. Therefore in Section 3.1 we augment the above statement with a combinatorial argument which yields Theorem 1.3.

Remark 3.1. A natural approach for proving Theorem 1.3 is to take

E′ = \{\{u, v\} : u, v ∈ V and d_{G}(u, v) = C\sqrt{log n}\} .

This idea is easily discarded through the following example: Let G = (V_{1} ⋃ V_{2}, E_{1} ⋃ E_{2} ⋃ E_{3}), where (V_{1}, E_{1}) and (V_{2}, E_{2}) are disjoint isomorphic (log n)-regular expander graphs with girth ≫ \sqrt{log n}, and E_{3} is a perfect matching between V_{1} and V_{2}. Consider a node u ∈ V_{1}. The number of nodes v ∈ V_{1} such that d_{G}(u, v) = C\sqrt{log n} is at least (log n)^{C\sqrt{log n}}. On the other hand, the number of nodes v ∈ V_{2} such that d_{G}(u, v) = C\sqrt{log n} is at most C\sqrt{log n} · (log n)^{C\sqrt{log n}−1}. Therefore, α(V, E′) ≤ \frac{C}{\sqrt{log n}}. Similar arguments show that other uniform constructions fail, such as taking pairs \{u, v\} with d_{G}(u, v) ≤ C\sqrt{log n} or taking random walks of length at most C\sqrt{log n}. It therefore seems that the edges in E′ have to be chosen judiciously.

3.1 Combinatorial preliminaries

As stated above, in Section 3.2 we prove a result which is weaker than Corollary 2.2. In this section we show that nevertheless, in the present setting such a weaker statement suffices to yield the full force of Theorem 1.3. Informally, the weaker result replaces edges and takes care of the expansion of large sets, but we may be left with a small set of vertices that has poor edge expansion. In this section we fix this poorly expanding set. Lemma 3.6 isolates the poorly expanding set. To fix it, we first reduce its size considerably by adding a large matching across the bad cut. The matching is constructed in Corollary 3.3. It may reduce the expansion by a constant factor, as shown in Lemma 3.5. For this reason, we cannot apply the matching argument iteratively on the remaining set. We therefore connect the remaining vertices iteratively to several vertices on the “good” side (Lemma 3.1), thus reducing the expansion by less than a constant factor in each iteration (Lemma 3.4). The cumulative effect of all the iterations reduces the expansion by another constant factor.

Lemma 3.1. Let G = (V, E) be a graph with h(G) ≥ \frac{1}{2} and t ∈ ℕ. Fix a subset S ⊆ V with 1 ≤ |S| ≤ \frac{|V |}{2(3/2)^{t}}. Then there exists a bipartite graph H = (S, V \ S, F) and a subset S′ ⊆ S such that the following conditions hold:

1. ∀{u, v} ∈ F, d_{G}(u, v) ≤ t.

2. |S \ S′| ≤ \frac{|S|}{(3/2)^{t/2}} .

3. ∀v ∈ V \ S, deg_{H}(v) ≤ 1.

4. ∀u ∈ S′, deg_{H}(u) ≥ ⌊(3/2)^{t/2}⌋ − 1.

Proof. Fix R ⊆ S of cardinality |R| > |S|/(3/2)^{t/2}. As h(G) ≥ \frac{1}{2}, we have that for every t ∈ ℕ, |{u ∈ V : d_{G}(R, u) ≤ t}| ≥ (3/2)^{t}|R| > |S|·(3/2)^{t/2}. Consider the following iteration, starting with S′, T, F = ∅: Find a pair of vertices u, v ∈ V such that u ∈ S \S′, v ∈ V \(S ⋃ T), and d_{G}(u, v) ≤ t. Place {u, v} in F, place v in T, and if currently deg_{H}(u) = ⌊(3/2)^{t/2}⌋ − 1, place u in S′. Terminate when no such pair of nodes exists. Notice that while R = S \ S′ satisfies |R| > |S|/(3/2)^{t/2}, then |{u ∈ V : d_{G}(R, u) ≤ t}| > |S| · (3/2)^{t/2} = |S| + |S| · ((3/2)^{t/2} − 1) ≥ |S| + |T |. Therefore, the iteration terminates with |R| ≤ |S|/(3/2)^{t/2}, and at that point the bipartite graph H = (S, V \S, F) satisfies all the required conditions.

Lemma 3.2. Let G = (V, E) be a connected graph with h(G) ≥ \frac{1}{2}, s_{1}, s_{2} ∈ ℕ, and X, Y ⊆ V satisfying |X| ≥ |V |/(3/2)^{s_{1}}, |Y | ≥ |V |/(3/2)^{s_{2}}. Then d_{G}(X, Y) ≤ s_{1} + s_{2} − 1.

Proof. Since h(G) ≥ \frac{1}{2}, the sets X′ = \{v ∈ V : d_{G}(v, X) ≤ s_{1} − 1\} and Y′ = \{v ∈ V : d_{G}(v, Y) ≤ s_{2} − 1} satisfy |X′|, |Y′| ≥ |V |/2. As G is connected, d_{G}(X′, Y′) ≤ 1.

Corollary 3.3. Let G = (V, E) be a connected graph with h(G) ≥ \frac{1}{2}, r ∈ ℕ and X, Y ⊆ V satisfying |X| ≤ min \{|Y |, \frac{|V |}{2}\}. Then there is Z ⊆ X and a one to one mapping M : Z → Y such that

1. For every v ∈ Z, d_{G}(v, M(v)) < 2r.

2. |X \ Z| ≤ |V |/(3/2)^{r}.

Proof. The proof is by induction on |X|. If |X| ≤ |V |/(3/2)^{r}, then there is nothing to prove. Otherwise, by Lemma 3.2, there are v ∈ X and M(v) ∈ Y such that d_{G}(v, M(v)) ≤ 2r − 1. Apply the induction hypothesis to X \ {v} and Y \ {M(v)}.

Lemma 3.4. Fix Δ > 0 and let G = (V, E) be a graph with |V | ≤ |E| ≤ Δ|V | and set α = min\{α(G), 1/Δ\}. Let k, m ∈ ℕ satisfy m ≤ \frac{|V |}{k^{2}}. Let V_{1}, …, V_{m} be disjoint k-vertex subsets of V. Construct a graph H = (W, F) by setting W = V ⋃{s_{1}, …, s_{m}}, where s_{1}, …, s_{m} are m new vertices, and F = E ⋃(⋃_{i=1}^{m} ⋃_{v∈V_{i}}{s_{i}, v}). Then

α(H) ≥ α (1 − \frac{3}{k} ) .

Proof. Notice that

\frac{|F |}{|W |} = \frac{|E| + mk}{|V | + m} ≤ \frac{|E| + mk}{|V |} ≤ \frac{|E| + |V |/k}{|V |} ≤ (1 + \frac{1}{k} ) \frac{|E|}{|V |}.

Fix S ⊆ W with 1 ≤ |S| ≤ |W |/2 and write A = S ∩ \{s_{1}, …, s_{m}\} and B = S ∩ V. If |A| ≥ \frac{2}{k}|S| then the number of edges leaving S is at least

k|A| − |B| ≥ 2|S| − |S| = |S| ≥ α\frac{|E|}{|V |}|S| ≥ α (1 − \frac{1}{k} ) \frac{|F |}{|W |}|S|.

Otherwise, |B| ≥ (1 − \frac{2}{k}) |S|, so if |B| ≤ |V |/2 then the number of edges leaving S is at least

α(G)\frac{|E|}{|V |}|B| ≥ α\frac{|E|}{|V |} (1 − \frac{2}{k} ) |S| ≥ α (1 − \frac{3}{k} ) \frac{|F |}{|W |}|S|.

If, on the other hand |B| > |V |/2, then by the definition of α(G) applied to V \ B, the number of edges leaving S is at least

α(G)\frac{|E|}{|V |}|V \ B| ≥ (1 − \frac{1}{k} ) α\frac{|F |}{|W |} (|V | − |S|)
≥ (1 − \frac{1}{k} ) α\frac{|F |}{|W |} · \frac{|V | − m}{|V | + m}|S|
≥ (1 − \frac{1}{k} ) α\frac{|F |}{|W |} · \frac{1 − 1/k^{2}}{1 + 1/k^{2}} |S|,

implying the required result.

Lemma 3.5. Fix Δ > 0 and let G = (V, E) be a graph with |V | ≤ |E| ≤ Δ|V |. Fix a set U with |U| ≤ \frac{|V |}{4} and U∩V = ∅ and let M : U → V be a one to one function. Construct a graph H = (W, F) by setting W = U ⋃ V and F = E ⋃(⋃_{u∈U}\{\{u, M(u)\}\}). Then α(H) ≥ min \{\frac{α(G)}{3}, \frac{1}{3Δ}\}.

Proof. Notice that \frac{|F |}{|W |} = \frac{|E|+|U|}{|V |+|U|} ≤ \frac{|E|}{|V |} ≤ Δ. Consider a set S ⊆ W with |S| ≤ \frac{1}{2}|W |. If |S ∩ U| ≥ \frac{2}{3}|S|, then

|\{u ∈ S ∩ U : M(u) ∉ S\}| ≥ \frac{1}{3}|S|.

Therefore, at least \frac{1}{3}|S| > \frac{|F |}{3Δ|W |}|S| edges leave S. Otherwise, |S ∩V | ≥ \frac{1}{3}|S|, implying that at least

α(G)\frac{|E|}{|V |} \frac{|S|}{3} ≥ \frac{α(G)|F |·|S|}{3|W |} edges in E leave S.

Lemma 3.6. Fix α, ε > 0 and let (V, F) be a graph with the property that for every S ⊆ V satisfying ε|V | ≤ |S| ≤ \frac{1}{2}|V |, |\{e ∈ F : |e ∩ S| = 1\}| ≥ α\frac{|F |}{|V |}|S|. Then there is U ⊆ V such that |V \ U| ≤ ε|V | and the graph G′ = (U, F′), where F′ = {e ∈ F : |e ∩ U| = 2}, has α(G′) ≥ (1 − ε)α.

Proof. Define a sequence of graphs (V_{0}, F_{0}), (V_{1}, F_{1}), …, (V_{k}, F_{k}) and a sequence of disjoint subsets S_{1}, …, S_{k} ⊆ V as follows. Put V_{0} = V and F_{0} = F. If α(V_{i}, F_{i}) ≥ (1 − ε)α set k = i. Otherwise, there is S_{i+1} ⊆ V_{i} for which

|\{e ∈ F_{i} : |e ∩ S_{i+1}| = 1\}| < (1 − ε)α\frac{|F_{i}|}{|V_{i}|}|S_{i+1}|.

Set V_{i+1} = V_{i} \ S_{i+1} and put F_{i+1} = {e ∈ F_{i} : e ∩ S_{i+1} = ∅}. We now show that |V_{k}| ≥ (1 − ε)|V |. For contradiction, let j be the smallest index in {1, 2, …, k} for which |V_{j}| < (1 − ε)|V |. Put S = ⋃_{i=1}^{j} S_{j}, so our assumption is that |S| > ε|V |. Then

|{e ∈ F : |e ∩ S| = 1}| ≤ ∑_{i=0}^{j−1} |{e ∈ F_{i} : |e ∩ S_{i+1}| = 1}|

< ∑_{i=0}^{j−1}(1 − ε)α\frac{|F_{i}|}{|V_{i}|}|S_{i+1}|

≤ ∑_{i=0}^{j−1}(1 − ε)α\frac{|F |}{(1 − ε)|V |}|S_{i+1}|

= α\frac{|F |}{|V |}|S|,

in contradiction to the conditions stated in the lemma. Now α(V_{k}, F_{k}) ≥ (1 − ε)α and |V_{k}| ≥ (1 − ε)|V |, so we can set U = V_{k} and F′ = F_{k}.

Lemma 3.7. Fix Δ, α, ε > 0. Let G = (V, E) be a graph with h(G) ≥ \frac{1}{2} and let F ⊆ \binom{V}{2} be a set of edges such that |V | ≤ |F | ≤ Δ|V | and (V, F) satisfies the conditions of Lemma 3.6. Then there exists F′′ ⊆ \binom{V}{2} such that the graph H = (V, F′′) satisfies α(H) ≥ min \{\frac{(1−ε)α}{300}, \frac{1}{1000Δ}\} and

max {d_{G}(u, v) : {u, v} ∈ F′′} ≤ max {2 log log |V |, max {d_{G}(u, v) : {u, v} ∈ F }} .

Proof. We will construct the graph H gradually. Initially, set H to be the graph G′ = (U, F′) from Lemma 3.6. So, |U| ≥ (1−ε)|V |, F′ ⊆ F, and α(G′) ≥ (1−ε)α. Fix an integer r ≥ 4, which will be determined later. By Corollary 3.3, there is a set Z ⊆ V \ U and a one to one mapping M : Z → U such that |V \ Z| ≤ |V |/(3/2)^{r} and for every u ∈ Z, d_{G}(u, M(u)) ≤ 2r. By Lemma 3.5, the graph H_{0} = (V_{0}, F_{0}) with V_{0} = U ⋃ Z and F_{0} = F′ ⋃\{\{u, M(u)\} : u ∈ Z\} has α(H_{0}) ≥ min \{\frac{(1−ε)α}{3}, \frac{1}{3Δ}\}. Put Z_{0} = V \ V_{0}. Now iterate the following step, starting with i = 0. Use Lemma 3.1 to generate a bipartite graph M_{i} = (Z_{i}, V_{i}, E_{i+1}) and a set Z_{i+1} ⊆ Z_{i} that satisfy the following conditions:

1. ∀{u, v} ∈ E_{i+1}, d_{G}(u, v) ≤ 2r.

2. |Z_{i+1}| ≤ |Z_{i}|/(3/2)^{r}.

3. ∀v ∈ V_{i}, deg_{M_{i}}(v) ≤ 1.

Figure 2: The iterative construction of the graphs H_{i}.

4. ∀u ∈ Z_{i} \ Z_{i+1}, deg_{M_{i}}(u) = ⌈(3/2)^{r−1}⌉.

This construction is described schematically in Figure 2

Set H_{i+1} = (V_{i} ⋃ Z_{i}, F_{i} ⋃ E_{i+1}). Notice that after k = ⌈\frac{3 log |V |}{r}⌉ steps, Z_{k} = ∅. Set H = H_{k}.

The number of edges in H is at most Δ|V |+ε|V |+ \frac{6|V | log |V |}{(3/2)^{r}} ≤ 10Δ|V |, provided r ≥ 10 log log |V |. Thus, by Lemma 3.4, for every i = 1, 2, …, k,

min \{α(H_{i}), \frac{1}{10Δ}\} ≥ min \{α(H_{i−1}), \frac{1}{10Δ}\} (1 − \frac{6}{(3/2)^{r}} ) .

Therefore, for r = ⌈10 log log |V |⌉,

α(H_{k}) ≥ min \{α(H_{0}), \frac{1}{10Δ}\} (1 − \frac{6}{(3/2)^{r}} )^{k}

≥ min \{\frac{(1 − ε)α}{3}, \frac{1}{10Δ}\} (1 − \frac{6}{(3/2)^{r}} )^{\frac{3 log |V |}{r}}
≥ min \{\frac{(1 − ε)α}{300}, \frac{1}{1000Δ}\} ,

as required.

Lemma 3.8. Let G = (V, E) be a graph and let π be a probability distribution on E. Assume that for every S ⊆ V such that \frac{|V |}{4} ≤ |S| ≤ \frac{|V |}{2}, π(\{e ∈ E : |e ∩ S| = 1\}) ≥ p. Then there exists a graph H = (V, F) such that F ⊆ E, |F | ≤ \frac{20}{p}|V |, and for every S ⊆ V with \frac{|V |}{4} ≤ |S| ≤ \frac{|V |}{2}, |{e ∈ F : |e ∩ S| = 1}| ≥ 5|V |.

Proof. Let k = ⌈10|V |/p⌉. Consider a sample F = {e_{1}, e_{2}, …, e_{k}} of E, where the e_{i} are independent, identically distributed random variables with Pr[e_{i} = e] = π(e). Consider a set of vertices S ⊆ V with \frac{|V |}{4} ≤ |S| ≤ \frac{|V |}{2}. Let X_{i} denote the indicator variable for the event |e_{i} ∩ S| = 1. Then Pr[X_{i} = 1] ≥ p. Trivially,

|{e ∈ F : |e ∩ S| = 1}| = ∑_{i=1}^{k} X_{i}.

Put X = ∑_{i} X_{i}. Then 𝔼[X] ≥ 10|V | and Pr[X < 5|V |] ≤ Pr[Y < 5|V |], where Y is distributed as the sum of k Bernoulli trials with success probability p. Using standard bounds on the deviation of Y, we get

Pr[X < 5|V |] ≤ Pr[Y < 5|V |] = Pr[Y < 𝔼[Y]/2] < e^{−𝔼[Y]/8} < e^{−|V |}.

On the other hand,

|\{S ⊆ V : \frac{|V |}{4} ≤ |S| ≤ \frac{|V |}{2}\}| ≤ 2^{|V |}.

Therefore, with probability approaching 1, F satisfies the required property.

In what follows we denote by B_{2} the unit ball of ℓ_{2}.

Lemma 3.9. Let G = (V, E) be a graph and δ, p, k > 0. Assume that for every f : V → B_{2} with \frac{1}{n^{2}} ∑_{u,v∈V} ∥f(u) − f(v)∥_{2} ≥ δ, there are u, v ∈ V such that d_{G}(u, v) ≤ k and ∥f(u) − f(v)∥_{2} ≥ p. Then there is a probability distribution π on {{u, v} : u, v ∈ V ∧ d_{G}(u, v) ≤ k} such that for every S ⊆ V with 4δ^{2/3}|V | ≤ |S| ≤ \frac{|V |}{2} we have that π(\{\{u, v\} : |\{u, v\} ∩ S| = 1\}) ≥ p^{2}.

Proof. Let F_{δ} be the set of all S ⊆ V with 4δ^{2/3}|V | ≤ |S| ≤ \frac{|V |}{2}. If S ∈ F_{δ} then we have that \frac{1}{|V |^{2}} ∑_{u,v∈V} [1_{S}(u) − 1_{S}(v)]^{2} ≥ 2δ^{2/3}. Denote by D_{F_{δ}} the set of all probability distributions on F_{δ}, i.e., the set of all (t_{S})_{S∈F_{δ}} such that t_{S} ≥ 0 and ∑_{S∈F_{δ}} t_{S} = 1. For t ∈ D_{F_{δ}} define f^{t} : V → ℝ^{F_{δ}} by f^{t}(v)_{S} = \sqrt{t_{S}} · 1_{S}(v). Then ∥f^{t}(v)∥_{2} ≤ 1 for all v ∈ V and \frac{1}{|V |^{2}} ∑_{u,v∈V} ∥f^{t}(u) − f^{t}(v)∥_{2}^{2} ≥ 2δ^{2/3}. Denoting D = {(x, y) ∈ X × X : ∥f(u) − f(v)∥_{2} ≥ δ^{1/3}} we have that |D| ≥ δ^{2/3}|V |^{2}. Hence \frac{1}{|V |^{2}} ∑_{u,v∈V} ∥f^{t}(u) − f^{t}(v)∥_{2} ≥ δ. By our assumption it follows that there are u, v ∈ G with d_{G}(u, v) ≤ k and ∥f(u) − f(v)∥_{2} ≥ p.

Now let Π be the set of all probability distributions π on {(u, v) ∈ V × V : d_{G}(u, v) ≤ k}. The Min-Max Theorem implies that

max_{π∈Π} min_{S∈F_{δ}} π({(u, v) : |{u, v} ∩ S| = 1}) ≥ min_{t∈D_{F_{δ}}} max_{π∈Π} ∑_{d_{G}(u,v)≤k} π(u, v)∥f^{t}(u) − f^{t}(v)∥_{2}^{2} ≥ p^{2},

as required.

Corollary 3.10. Let G = (V, E) be an n-vertex graph satisfying h(G) ≥ \frac{1}{2}. Assume that there exist constants c, C > 0 such that for every f : V → B_{2} satisfying \frac{1}{n^{2}} ∑_{u,v∈V} ∥f(u) − f(v)∥_{2} ≥ \frac{1}{64} there are u, v ∈ V with d_{G}(u, v) ≤ C\sqrt{log n} and ∥f(u) − f(v)∥_{2} ≥ c. Then there are edges E′ on V such that for every \{u, v\} ∈ E′, d_{G}(u, v) = O(C\sqrt{log n}) and α(V, E′) = Ω(c^{2}).

Proof. By Lemma 3.9 there is a probability distribution π on {{u, v} : u, v ∈ V ∧ d_{G}(u, v) ≤ C\sqrt{log n}\} such that for every S ⊆ V with \frac{n}{4} ≤ |S| ≤ \frac{n}{2} we have that π(\{\{u, v\} : |\{u, v\} ∩ S| = 1}) ≥ c^{2}. By Lemma 3.8 there are edges F on V such that |F | ≤ 20n/c^{2}, for every {u, v} ∈ F, d_{G}(u, v) ≤ C\sqrt{log n} and for every S ⊆ V with \frac{n}{4} ≤ |S| ≤ \frac{n}{2}, |\{e ∈ F : |e ∩ S| = 1\}| ≥ 5|V |.

Now, the graph (V, F) satisfies the conditions of Lemma 3.6 with ε = \frac{1}{4} and α = \frac{c^{2}}{4} . So, Lemma 3.7 yields new edges F′′ on V for which α(V, F′′) = Ω(c^{2}) and for every {u, v} ∈ F′′, d_{G}(u, v) = O(C\sqrt{log n}).

3.2 The Euclidean argument

In what follows S^{d−1} denotes the unit Euclidean sphere in ℝ^{d} and B_{2}^{d} denotes the unit Euclidean ball in ℝ^{d}. The normalized Haar measure on S^{d−1} is denoted by σ.

By Corollary 3.10, Theorem 1.3 will be proved once we establish the following result, the proof of which is based on the chaining argument from [2].

Proposition 3.11. Let G = (V, E) be an n-vertex graph with h(G) ≥ \frac{1}{2} and δ ∈ (0, 2]. Assume that f : V → B_{2}^{d} satisfies

\frac{1}{n^{2}} ∑_{u,v∈V} ∥f(u) − f(v)∥_{2} ≥ δ.  (4)

Then there are u, v ∈ V such that

d_{G}(u, v) ≤ 10[log(750/δ)] · \sqrt{log n} and ∥f(u) − f(v)∥_{2} ≥ \frac{δ}{1000\sqrt{log(4/δ)}}.

Before we proceed with the proof, we present an informal description of the chaining argument. The basic idea is that if there is a set A ⊆ \binom{V}{2} of nearby pairs of vertices of G such that, for almost every direction y ∈ S^{d−1}, there are pairs of vertices {u, v} ∈ A with projections ⟨y, f(u)⟩ and ⟨y, f(v)⟩ far apart, then there is a pair of vertices u, v with far apart f(u) and f(v). In order to construct the set of pairs A, one begins with pairs that are very close in G but have projections that are not far enough (Lemma 3.13). Then, these pairs are iteratively chained to create new pairs that are more distant in G and have better projections. In each iteration, the measure of good directions is boosted using measure concentration, and the number of pairs is boosted using the vertex expansion of G.

We begin with the following simple numerical fact:

Lemma 3.12. Fix η ∈ (0, 1) and let X ⊆ ℝ be an n-point subset of the the real line satisfying

|{(x, y) ∈ X × X : |x − y| ≥ a}| ≥ ηn^{2}.

Then there exist A, B ⊆ X with |A|, |B| ≥ (\frac{1−\sqrt{1−η}}{2} ) n ≥ \frac{η}{4}n and such that |x| ≥ |y| + \frac{a}{2} for all x ∈ B and y ∈ A.

Proof. Let m be a median of X. Write k = |X ∩ (m − a/2, m + a/2)|. Then k^{2} ≤ (1 − η)n^{2}, i.e., k ≤ \sqrt{1 − η}n. It follows that either |X ∩ (−∞, m − a/2]| ≥ (\frac{1−\sqrt{1−η}}{2} ) n or |X ∩ [m + a/2, ∞)| ≥

(\frac{1−\sqrt{1−η}}{2} ) n. In the first case take A = X ∩ (−∞, m − a/2] and B = X ∩ [m, ∞). In the second case take A = X ∩ (−∞, m], B = X ∩ [m + a/2, ∞).

Lemma 3.13. Let Z be an n-point subset of B_{2}^{d} such that

\frac{1}{n^{2}} ∑_{z,w∈Z} ∥z − w∥_{2} ≥ δ.

Then

σ \{y ∈ S^{d−1} : |\{(z, w) ∈ Z × Z : |⟨z − w, y⟩| ≥ \frac{δ}{16\sqrt{d}}\}| ≥ \frac{δn^{2}}{2} \} ≥ \frac{1}{4}.

Proof. Let D = \{(z, w) ∈ Z × Z : ∥z − w∥_{2} ≥ \frac{δ}{2}\}. Since diam(Z) ≤ 2, |D| ≥ \frac{δ}{4}n^{2}. If (z, w) ∈ D then a simple calculation yields

σ \{y ∈ S^{d−1} : |⟨z − w, y⟩| ≥ \frac{δ}{16\sqrt{d}}\} ≥ \frac{1}{2}.

Hence

∫_{S^{d−1}} (\frac{1}{n^{2}} ∑_{z,w∈Z} 1_{\{y∈S^{d−1}: |⟨z−w,y⟩|≥δ/(16\sqrt{d})\}}) dσ(y) ≥ \frac{1}{2},

implying the required result.

Lemma 3.14. Let G and f be as in the statement of Proposition 3.11. There exists a subset U ⊆ V satisfying |U| ≥ \frac{δn}{130} with the following property. For every y ∈ S^{d−1} there is W_{y} ⊆ U and a one to one mapping M_{y} : W_{y} → U \ W_{y} such that, for every v ∈ W_{y}, we have d_{G}(v, M_{y}(v)) ≤ 6 log(16/δ) and

⟨f(M_{y}(v)) − f(v), y⟩ ≥ \frac{δ}{32\sqrt{d}},  (5)

and for every v ∈ U,

σ\{y ∈ S^{d−1} : v ∈ W_{y}\} ≥ \frac{δ}{360}.  (6)

Proof. By Lemma 3.13 applied to f(V) ⊆ B_{2}^{d}, there exists a subset T ⊆ S^{d−1} such that σ(T) ≥ \frac{1}{4} and for every y ∈ T there are A_{y}, B_{y} ⊆ V such that |A_{y}|, |B_{y}| ≥ \frac{δn}{8} and for every p ∈ B_{y}, q ∈ A_{y},

⟨f(p), y⟩ ≥ ⟨f(q), y⟩ + \frac{δ}{32\sqrt{d}}.

By Corollary 3.3 there is a subset A_{y}^{1} ⊆ A_{y} with |A_{y}^{1}| ≥ \frac{δn}{16} and a one to one mapping M_{y} : A_{y}^{1} → B_{y} such that for every v ∈ A_{y}^{1}, d_{G}(v, M_{y}(v)) ≤ 6 log(16/δ).

Fix a subset T′ ⊆ T for which σ(T′) ≥ \frac{1}{8} and T′ ∩ (−T′) = ∅. We will construct inductively sets V_{1} = V ⊇ V_{2} ⊇ ⋯ ⊇ V_{k} as follows. Assuming V_{i} has been defined, denote

A_{y}^{i} = A_{y}^{1} ∩ V_{i} ∩ [(M_{y})^{−1}(M(A_{i}^{1}) ∩ V_{i})].

For every v ∈ V_{i} write

S_{v}^{i} = {y ∈ T′ : v ∈ A_{y}^{i} ⋃ M_{y}(A_{y}^{i})}.

If there is v ∈ V_{i} for which σ(S_{v}^{i}) < \frac{δ}{360}, define V_{i+1} = V \ \{v\}. This procedure ends when for every v ∈ V_{k} we have σ(S_{k}^{i}) ≥ \frac{δ}{360}. We choose U = V_{k} and for all y ∈ T′, W_{y} = A_{y}^{k}. We symmetrize by setting, for all y ∈ −T′, W_{y} = M_{−y}(W_{−y}) and M_{y} = (M_{−y})^{−1}. With these definitions, the construction implies that (5) and (6) are satisfied.

It remains to bound |U| from below. Fix i < k and write {u} = V_{i} \ V_{i+1} Observe that

∑_{v∈V_{i+1}} σ(S_{v}^{i+1}) = ∑_{v∈V_{i}} σ(S_{v}^{i}) − σ(S_{u}^{i}) −

∑_{v∈V_{i+1}}[σ{y ∈ T′ : v ∈ A_{y}^{i} ∧ u = M_{y}(v)} + σ{y ∈ T′ : u ∈ A_{y}^{i} ∧ v = M_{y}(u)}]

= ∑_{v∈V_{i}} σ(S_{v}^{i}) − 2σ(S_{u}^{i}) ≥ ∑_{v∈V_{i}} σ(S_{v}^{i}) − \frac{δ}{130}.

By induction we have

|U| ≥ ∑_{v∈V_{k}} σ(S_{v}^{k}) ≥ ∑_{v∈V} σ(S_{v}^{1}) − \frac{δ(n − |U|)}{130} = ∫_{T′} 2|A_{y}^{1}|dσ(y) − \frac{δ(n − |U|)}{130} ≥ \frac{δn}{64} − \frac{δ(n − |U|)}{130},

implying the required estimate.

Proof of Proposition 3.11. Assume for the sake of contradiction that, for every u, v ∈ V with d_{G}(u, v) ≤ 10[log(750/δ)] · \sqrt{log n}, we have ∥f(u) − f(v)∥_{2} ≤ \frac{δ}{1000\sqrt{log(4/δ)}}. Let U be as in

Lemma 3.14. We claim that this implies that for every i ≤ \sqrt{log n} there is a subset Y_{i} ⊆ U with |Y_{i}| ≥ \frac{|U|}{2} such that, for every v ∈ Y_{i},

σ {y ∈ S^{d−1} : ∃u ∈ U s.t. d_{G}(u, v) ≤ 10[log(750/δ)] · i and
⟨f(u) − f(v), y⟩ ≥ \frac{δi}{64\sqrt{d}}\} ≥ (1 − \frac{δ}{500}) .  (7)

Assuming this for the moment, we conclude the proof of Proposition 3.11 as follows. Set k = ⌊\sqrt{log n}⌋, take any v ∈ Y_{k} and consider the ball B = B_{G}(v, 10[log(750/δ)]·k) = \{u ∈ V : d_{G}(u, v) ≤ 10[log(750/δ)] · k\} in G. For every u ∈ B, our assumption implies that ∥f(u) − f(v)∥_{2} ≤ \frac{δ}{1000}, so that

σ \{y ∈ S^{d−1} : ⟨f(u) − f(v), y⟩ ≥ \frac{δk}{64\sqrt{d}}\} < \frac{1}{n^{3}} .

By the union bound, this contradicts (7).

It remains to prove (7). The proof is by induction on i. For i = 0 the claim is vacuous. Assuming the existence of Y_{i} for some i ≤ \sqrt{log n} − 1, we will deduce the existence of Y_{i+1}.

Fix v ∈ Y_{i} and denote

T_{v} = \{y ∈ S^{d−1} : ∃u ∈ U s.t. d_{G}(u, v) ≤ 10[log(750/δ)] · i and ⟨f(u) − f(v), y⟩ ≥ \frac{δi}{64\sqrt{d}}\} ,

so that by the inductive hypothesis σ(T_{v}) ≥ 1 − δ/500. It follows from the definition that there is a function N_{v} : T_{v} → B_{G}(v, 10[log(750/δ)] · i) ∩ U such that for every y ∈ T_{v}

⟨f(N_{v}(y)) − f(v), y⟩ ≥ \frac{δi}{64\sqrt{d}}.

By (6) there is a subset T′_{v} ⊆ T_{v} with σ(T′_{v}) ≥ \frac{δ}{1000} such that, for every y ∈ T′_{y}, v ∈ W_{−y}. Observe that for y ∈ T′_{v}, d_{G}(M_{−y}(v), N_{v}(y)) ≤ 10[log(750/δ)] · i + 6 log(16/δ) and

⟨f(N_{v}(y)) − f(M_{−y}(v)), y⟩ = ⟨f(N_{v}(y)) − f(v), y⟩ + ⟨f(v) − f(M_{−y}(v)), y⟩ ≥ \frac{δi}{64\sqrt{d}} + \frac{δ}{32\sqrt{d}}.

For every u ∈ U consider the set

K_{u} = {y ∈ S^{d−1} : ∃v ∈ Y_{i} s.t. y ∈ T′_{v} and u = M_{−y}(v)},

and define

Z = \{u ∈ U : σ(K_{u}) ≥ \frac{δ}{4000}\} .

Now we have

∑_{v∈Y_{i}} σ(T′_{v}) ≥ \frac{δ|Y_{i}|}{1000} ≥ \frac{δ|U|}{2000}.

On the other hand, since M_{−y} is one to one,

∑_{v∈Y_{i}} σ(T′_{v}) = ∫_{S^{d−1}} |{v ∈ Y_{i} : y ∈ T′_{v}}|dσ(y)

= ∫_{S^{d−1}} |{u ∈ U : ∃v ∈ Y_{i} s.t. y ∈ T′_{v} ∧ u = M_{−y}(v)}|dσ(y)
= ∑_{u∈U} σ(K_{u}) ≤ |Z| + \frac{δ|U|}{4000}.

It follows that |Z| ≥ \frac{δ|U|}{4000}. Fix u ∈ Z and define

L_{u} = {y ∈ S^{d−1} : ∃v ∈ U ∩ B_{G}(u, 10[log(750/δ)] · i + 6 log(16/δ)) and

⟨f(v) − f(u), y⟩ ≥ \frac{δi}{64\sqrt{d}} + \frac{δ}{50\sqrt{d}}\}

We claim that L_{u} ⊇ (K_{u})_{7\sqrt{[log(4/δ)]/d}} (recall that A_{r} denotes the Euclidean r-neighborhood of a set A). Indeed, if y ∈ K_{u} then, by the definition of K_{u}, there is w ∈ U ∩ B_{G}(u, 10[log(750/δ)] · i + 6 log(16/δ)) such that ⟨f(w) − f(u), y⟩ ≥ \frac{δi}{64\sqrt{d}} + \frac{δ}{32\sqrt{d}}. Observe that (by our contrapositive

assumption), ∥f(w) − f(u)∥_{2} ≤ \frac{δ}{1000\sqrt{log(4/δ)}}. Fix z ∈ S^{d−1} with ∥z − y∥_{2} ≤ 7\sqrt{\frac{log(4/δ)}{d}}. Then,

⟨f(w) − f(u), z⟩ ≥ ⟨f(w) − f(u), y⟩ − ∥f(w) − f(u)∥_{2} · ∥z − y∥_{2}
≥ \frac{δi}{64\sqrt{d}} + \frac{δ}{32\sqrt{d}} − \frac{7δ}{1000\sqrt{log(4/δ)}} · \sqrt{\frac{log(4/δ)}{d}}
≥ \frac{δi}{64\sqrt{d}} + \frac{δ}{50\sqrt{d}}.

By concentration of measure on S^{d−1}, it follows that

σ(L_{u}) ≥ 1 − \frac{8000}{δ}e^{− \frac{49}{2} log(4/δ)} > 1 − \frac{δ}{1000}.

We are almost done, except for the fact that Z is too small. This is where the lower bound on h(G) is used (again). Define Z̃ = \{v ∈ V : d_{G}(v, Z) ≤ 6 log(750/δ)\}. We claim that |Z̃ ∩ U| ≥ \frac{|U|}{2}. Otherwise, denote A = V \ Z̃. Since h(G) ≥ \frac{1}{2},

|\{v ∈ V : d_{G}(v, Z) ≤ 3 log(740/δ)\}| > min \{(\frac{3}{2})^{3 log(750/δ)} |Z|, \frac{n}{2}\}

≥ min \{(\frac{3}{2})^{3 log(750/δ)} \frac{δ|U|}{4000}, \frac{n}{2}\}

≥ min \{(\frac{750}{δ})^{2} \frac{δ^{2}n}{130 · 4000}, \frac{n}{2}\} = \frac{n}{2},

and similarly (since |A| ≥ |U|/2 ≥ δn/360), |\{v ∈ V : d_{G}(v, A) ≤ 3 log(740/δ)\}| > \frac{n}{2}. This implies that there is some v ∈ V for which d_{G}(v, Z) ≤ 3 log(740/δ) and d_{G}(v, A) ≤ 3 log(740/δ), which contradicts the fact that Z̃ ∩ A = ∅.

We define Y_{i+1} = Z̃ ∩ U. It remains to show that (7) holds for every v ∈ Y_{i+1}. Indeed, there exists u ∈ Z such that d_{G}(u, v) ≤ 6 log(740/δ) and

σ {y ∈ S^{d−1} : ∃w ∈ U s.t. d_{G}(w, u) ≤ 10[log(750/δ)] · i + 6 log(16/δ) and

⟨f(w) − f(u), y⟩ ≥ \frac{δi}{64\sqrt{d}} + \frac{δ}{50\sqrt{d}}\} ≥ 1 − \frac{δ}{1000}.

It follows that

σ {y ∈ S^{d−1} : ∃w ∈ U s.t. d_{G}(w, v) ≤ 10[log(750/δ)] · (i + 1) and

⟨f(w) − f(v), y⟩ ≥ \frac{δi}{64\sqrt{d}} + \frac{δ}{50\sqrt{d}} − ⟨f(u) − f(v), y⟩\} ≥ 1 − \frac{δ}{1000}.

But, since ∥f(u) − f(v)∥_{2} ≤ \frac{δ}{1000\sqrt{log(4/δ)}}, it follows that

σ \{y ∈ S^{d−1} : ⟨f(u) − f(v), y⟩ ≥ (\frac{1}{50} − \frac{1}{64}) \frac{δ}{\sqrt{d}}\} < \frac{δ}{1000},

implying (7). This completes the proof of Proposition 3.11, and hence of Theorem 1.3.

References

[1] Alon, N. and Spencer, J. The Probabilistic Method, Wiley-Interscience, New York, second edition, 2000.

[2] Arora, S., Rao, S. and Vazirani, U., Expander flows, geometric embeddings and graph partioning, In Proceedings of the 36th Annual ACM Symposium on the Theory of Computing, 222–231, 2004.

[3] Bartal, Y, Linial, N., Mendel, M. and Naor, A., On metric Ramsey-type phenomena. To appear in the Annals of Mathematics, 2004.

[4] Beurling A., and Ahlfors, L., The boundary correspondence under quasiconformal mappings. Acta Math. 96, 125–142, 1956.

[5] Deza, M. M. and Laurent, M., Geometry of cuts and metrics. Springer-Verlag, Berlin, 1997.

[6] Feige, U. and Schechtman, G., On the optimality of the random hyperplane rounding technique for MAX CUT, Random Structures and Algorithms 20, 403–440, 2002.

[7] Gromov, M., Metric structures for Riemannian and non-Riemannian spaces, Birkhaüser 1999.

[8] Grötschel, M., Lovász, L. and Schrijver A., Geometric algorithms and combinatorial optimization. Springer-Verlag, 1993.

[9] Heinonen, J., Lectures on Analyis on Metric Spaces, Universitext, Springer-Verlag, New-York, 2001.

[10] Lee, J. R., On distance scales, embeddings, and efficient relaxations of the cut cone. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005.

[11] Leighton, F.T. and Rao, S., Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM 46, 787–832, 1999.

[12] Matoušek, J., Embedding expanders into ℓ_{p}, Israel J. Math. 102, 189-197, 1997.

[13] Milman, V. and Schechtman, G., Assymptotic theory of finite dimensional normed spaces, Springer-Verlag, Berlin 1986.

[14] Tukia, P. and Väisälä, J., Quasisymmetric embeddings of metric spaces, Ann. Acad. Sci. Fenn. Ser. A I. Math. 5, 97–114, 1980.