Girth and Euclidean Distortion

Nathan Linial ^{∗}  Avner Magen ^{†}  Assaf Naor ^{‡}

November 1, 2001

Abstract

Let G be a k-regular graph, k ≥ 3, with girth g. We prove that every embedding f : G → ℓ_{2} has distortion Ω(\sqrt{g}). Two proofs are given, one based on Markov Type [1] and the other on quadratic programming. In the core of both proofs are some Poincaré-type inequalities on graph metrics.

1 Introduction

Finite metric spaces and their embeddings in other metric spaces have been intensively investigated in recent years. For metric spaces (X, d_{X}) and (Y, d_{Y}), and an embedding f : X → Y we define the distortion of f by:

dist(f) = sup_{x,y∈X} \frac{d_{Y} (f(x), f(y))}{d_{X}(x, y)} · sup_{x,y∈X} \frac{d_{X}(x, y)}{d_{Y} (f(x), f(y))}.

We denote by c_{Y} (X, d) the least distortion with which (X, d) may be embedded in Y. For p ≥ 1 we denote c_{p}(X, d) = c_{ℓ_{p}}(X, d). A special case of interest is when Y is the Euclidean space ℓ_{2}. In this case, a fundamental result of Bourgain [5] states that c_{2}(X, d) = O(log n) for every n-point metric space (X, d).

One natural source for examples of metrics comes from graphs. A graph G induces a metric d_{G} on its vertex set, where d_{G}(u, v) is the length of the shortest path in G joining u and v. Special families of graphs define special families of metrics, e.g. expander graph metrics are studied in [5, 14, 13], tree metrics in [2, 6, 12, 15], metrics of graphs with forbidden minors in [17, 9, 10] and many more. Here we consider regular graphs with constant degree, and wish to study the Euclidean distortion of these graphs as a function of their girth.

In [11], Bourgain’s upper bound for the Euclidean distortion was shown to be tight. In fact, the Euclidean distortion of an n point constant degree expander is Ω(log n). This fact is striking since for any graph G, the trivial bound c_{2}(G, d_{G}) ≤ diam(G) follows by embedding G as a simplex in ℓ_{2}. When G is an n-point expander, diam(G) = O(log n), so that up to constant factors, the best way to embed an expander in Hilbert space is to ignore its structure altogether and embed it as if it were a clique! A new proof of this phenomenon follows from the results presented in this article.

In most examples we know, metrics are far from being Euclidean, since they include ”too many” triples for which the triangle inequality holds as (a near) equality. The simplest example is K_{1,3} that cannot be embedded isometrically in Euclidean space, since there cannot be three geodesics between three different points that meet in their interior. For the hypercube of dimension m, there are m! geodesics between every pair of antipodes, and consequently we get a large Euclidean distortion [8, 13].

∗Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. E-mail: nati@cs.huji.ac.il. Supported in part by grants from the Israeli Academy of Sciences and the Binational Science Foundation Israel-USA.

†Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. E-mail: avnerma@cs.huji.ac.il.

‡Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel. E-mail: naor@math.huji.ac.il. Supported in part by the Binational Science Foundation Israel-USA and the Clore Foundation. This work is part of a Ph.D. thesis being prepared under the supervision of Professor Joram Lindenstrauss.

It is known that for a tree T on n vertices, c_{2}(T, d_{T}) = O(\sqrt{log log n}), and this is bound is tight, as the Euclidean distortion of the complete binary tree on n vertices is θ(\sqrt{log log n}) (see [6, 15, 12]). Motivated by this, Linial, London and Rabinovich considered regular graphs with constant degree (bigger than 2) and with girth g. Any such graph contains isometrically a tree of depth g/2 − 1, which immediately gives the lower bound c_{2}(G, d_{G}) = Ω(\sqrt{log g}). Unlike the complete binary tree example, every vertex in the graph is a root of such a tree. In [11], Linial et. al. conjecture that c_{2}(d_{G}) = Ω(g). In this paper we prove c_{2}(d_{G}) = Ω(\sqrt{g}).

A key ingredient (sometimes stated explicitly and often implicit in the proofs) in all the existing proofs of lower bounds for the Euclidean distortion of graphs is a Poincaré type inequality. Let G be a graph, and take any function f : V (G) → ℓ_{2}. A Poincaré type inequality bounds the average size of {∥f(u) − f(v)∥_{2}}_{u,v∈V (G)} in terms of its average “gradient” {∥f(u) − f(v)∥}_{[u,v]∈E(G)}. Such an inequality measures how often an equality holds in the triangle inequality. A lower bound on the Euclidean distortion of an n-point k-regular expander with conductance Φ, G, can be derived from the following Poincaré inequality for functions f : V (G) → ℝ (see [14]):

∑_{u,v∈V (G)} |f(u) − f(v)| ≤ \frac{n − 1}{Φ} ∑_{[u,v]∈E(G)} |f(u) − f(v)|.

For the embeddability of the Hamming cube D_{n} = {0, 1}^{n} in a metric space (X, d_{X}), the following Poincaré inequality is relevant.

∑_{d_{H}(u,v)=n} d_{X}^{2}(f(u), f(v)) ≤ K^{2}n^{\frac{2}{p} −1} ∑_{[u,v]∈E(D_{n})} d_{X}^{2}(f(u), f(v)),

where d_{H} is the Hamming metric, and f : D_{n} → X is any function. When such an inequality holds, for some p > 0, for every n and with K independent of n and f, we say that (X, d_{X}) has metric type p with constant K. This fundamental notion was introduced in [7], where it was proved to essentially control the growth of c_{X}(D_{n}). When X is a Banach space, metric type is studied via an important Poincaré inequality due to Pisier (See [16]. See also [21] for a different proof, and [20] for an improvement when X is the real line). We refer also to [7, 16] for a related Poincaré inequality known as Enflo-type, or roundness.

Let T be the complete binary tree of depth N. The following Poincaré inequality is implicit in [12], where a new proof of the estimate c_{2}(T_{N}) = Ω(\sqrt{log N}) is obtained. Denote by r the root of T, and for every integer k let F_{k} be the set of all unordered pairs of vertices {u, v} ⊂ V (T) such that d_{T} (u, r) = d_{T} (v, r) and d_{T} (u, v) = 2^{k}. Then, for every f : V (T) → ℝ:

∑_{k=1}^{⌊log_{2} N⌋} ∑_{{u,v}∈F_{k}} 2^{d_{T} (u,r)−2^{k}−2k} · |f(u) − f(v)|^{2} ≤ C ∑_{[u,v]∈E(T)} 2^{N−d_{T} (u,r)}|f(u) − f(v)|^{2},

where C is an absolute constant.

This paper further develops the above theme. We introduce two Poincaré type inequalities which are useful in the search of lower bounds for Euclidean distortion of graphs with large girth. The first is the notion of Markov type, due to K. Ball [1], which concerns the wandering of symmetric Markov chains whose state set is a metric space. We refer to section 2 for the definition. We also prove the following theorem, which can be viewed as a new Poincaré type inequality :

Theorem 1.1 Let H be a Hilbert space and G be a k-regular graph, k ≥ 3, with girth g. Fix some 1 < s < g/2. For every f : V (G) → H the following inequality holds:

∑_{d_{G}(u,v)=s} ∥f(u) − f(v)∥^{2} ≤ Cs(k − 1)^{s−1} · ∑_{[u,v]∈E(G)} ∥f(u) − f(v)∥^{2},

where C is an absolute constant.

If, in addition, the graph G has a spectral gap, we can prove a stronger inequality. This leads to a new simple proof of the tightness of Bourgain’s embedding theorem:

Theorem 1.2 Let H be a Hilbert space and G be a k regular graph, k ≥ 3, with girth g and spectral gap ϵ > 0. Fix some 1 < s < g/2. For every f : V (G) → H the following inequality holds:

∑_{d_{G}(u,v)=s} ∥f(u) − f(v)∥^{2} ≤ C(k − 1)^{s} · \frac{1 − e^{−Cϵs/k}}{ϵ} · ∑_{[u,v]∈E(G)} ∥f(u) − f(v)∥^{2},

where C is an absolute numerical constant.

We apply the above inequalities to prove our main result:

Theorem 1.3: There is a universal constant C > 0 such that c_{2}(G) > C\sqrt{g} for every k-regular (k > 2) graph G with girth g. If, in addition, G has a spectral gap ϵ > 0 then:

c_{2}(G) ≥ \frac{Cg}{\sqrt{min \{g, \frac{k}{ϵ} \}}}.

Remark: It is well known and not hard to show by probabilistic arguments that for every integer k ≥ 3, there is an ϵ = ϵ_{k} > 0 and n_{0} = n_{0}(k) such that if n ≥ n_{0} and kn is even, there exist k-regular graphs of order n, spectral gap greater than ϵ and girth Ω(log n). In view of Theorem 1.3 these graphs show that Bourgain’s upper bound is tight. A curious feature of our estimate is that the lower bound for the Euclidean distortion of constant degree graphs with girth g, does not depend on the graph’s degree.

This paper contains two proofs for the first part of Theorem 1.3. We first present a proof based on the notion of Markov type. Next, we prove the inequalities in Theorems 1.1 and 1.2 to deduce the full statement of Theorem 1.3. This proof is based on quadratic programming. In section 4 we discuss the interrelations between the two methods.

2 A proof based on the concept of Markov Type

The first proof we present is based on the important notion of Markov type, due to K. Ball [1]. This concept is a Lipschitz invariant of metric spaces. It is related to other “types” that are central to the modern theory of Banach spaces. The basic assumption of this concept can also be viewed as a Poincaré inequality on metric spaces. Although we will see later that the Markov type method cannot yield the second statement in Theorem 1.3, it does give a simple and conceptual proof of the first statement. We first recall some definitions from [1].

Let (X, d) be a metric space. A symmetric Markov chain on X is a Markov chain {Z_{k}}_{k=0}^{∞} on a state space {x_{1}, ...x_{m}} ⊂ X with a symmetric transition matrix and such that Z_{0} is uniformly distributed on {x_{1}, ..., x_{m}}. In other words, there is a m × m symmetric stochastic matrix A = (a_{ij}) such that for all k, P (Z_{k+1} = x_{j}|Z_{k} = x_{i}) = a_{ij} and P (Z_{0} = x_{i}) = \frac{1}{m}. For p > 0 and an integer T let M_{p}(X, T) be the smallest constant C > 0 such that for every symmetric Markov chain on X, {Z_{k}}_{k=1}^{∞}

𝔼 d^{p}(Z_{T} , Z_{0}) ≤ C^{p}T 𝔼 d^{p}(Z_{1}, Z_{0}).

We say that (X, d) has Markov type p if M_{p}(X) := sup_{T} M_{p}(X, T) < ∞. In this case M_{p}(X) is called the Markov type p constant of X.

The space L_{2} has Markov type 2 with constant 1, as shown in [1]. For the sake of completeness, we prove here a somewhat stronger and rather intuitive claim. We first observe that the Markov type 2 property for ℝ implies, by integration, the same conclusion for L_{2}. For symmetric Markov chains on ℝ we prove the following negative correlation inequality that implies Markov type 2. Let {Z_{k}}_{k=1}^{∞} be a symmetric Markov chain with transition matrix A and state space {x_{1}, ..., x_{m}} ⊂ ℝ. The symmetry assumption makes it intuitively plausible that Z_{T} − Z_{T −1} and Z_{T −1} − Z_{0} must be negatively correlated. To prove this, notice that Z_{k} is uniformly distributed on {x_{1}, ..., x_{m}}, for every k. Since A is symmetric and stochastic, its spectrum is in [−1, 1], and we deduce that (I − A)(I − A^{k}) is positive semi-definite for every k. Therefore,

𝔼(Z_{T} − Z_{T −1})(Z_{T −1} − Z_{0}) = 𝔼Z_{T} Z_{T −1} − 𝔼Z_{T} Z_{0} − 𝔼Z_{T −1}^{2} + 𝔼Z_{T −1}Z_{0} =

= \frac{1}{m} [ ∑_{i,j=1}^{m}(A)_{ij}x_{i}x_{j} − ∑_{i,j=1}^{m}(A^{T})_{ij}x_{i}x_{j} − ∑_{i=1}^{m} x_{i}^{2} + ∑_{i,j=1}^{m}(A^{T −1})_{ij}x_{i}x_{j}] =

= −\frac{1}{m}⟨(I + A^{T} − A − A^{T −1})x, x⟩ = −\frac{1}{m}⟨(I − A)(I − A^{T −1})x, x⟩ ≤ 0,

where x = (x_{1}, ..., x_{m}). Hence :

𝔼(Z_{T} − Z_{0})^{2} = 𝔼(Z_{T −1} − Z_{0} + Z_{T} − Z_{T −1})^{2} =
= 𝔼(Z_{T −1} − Z_{0})^{2} + 2𝔼(Z_{T} − Z_{T −1})(Z_{T −1} − Z_{0}) + 𝔼(Z_{T} − Z_{T −1})^{2} ≤
≤ 𝔼(Z_{T −1} − Z_{0})^{2} + 𝔼(Z_{1} − Z_{0})^{2}.

By summing this inequality over T = 1, ..., N, we deduce that the real line has Markov type 2 with constant 1.

The following simple consequence of the above analysis will be useful for us:

Corollary 2.1: For every metric space (X, d), c_{2}(X, d) ≥ M_{2}(X).

Proof: Fix some embedding f : X → L_{2} such that 1/D ≤ ∥f(x) − f(y)∥/d(x, y) ≤ 1 for every x, y ∈ X. For every symmetric Markov chain {Z_{k}}_{k=0}^{∞} on X, the Markov type 2 property of L_{2} applied to the Markov chain {f(Z_{k})}_{k=0}^{∞} gives:

\frac{1}{D^{2}} 𝔼 d^{2}(Z_{T} , Z_{0}) ≤ 𝔼∥f(Z_{T}) − f(Z_{0})∥^{2} ≤ T 𝔼∥f(Z_{1}) − f(Z_{0})∥^{2} ≤ T 𝔼 d^{2}(Z_{1}, Z_{0}),

so that D ≥ M_{2}(X).

The first assertion in Theorem 1.3 follows from the following:

Proposition 2.2 Let G be a k-regular graph with girth g. Then

M_{2}(G) ≥ \frac{k − 2}{k}\sqrt{⌈\frac{g}{2} − 1⌉}.

Proof: Consider the symmetric Markov chain {Z_{t}}_{t=0}^{∞} that corresponds to the canonical random walk on G. Namely, Z_{0} is uniformly distributed on V (G) and P (Z_{t+1} = v|Z_{t} = u) equals \frac{1}{k} if u and v are neighbors, and 0 otherwise. Note that every vertex v ∈ V (G) is the root of a k-regular tree of depth g/2 (or more precisely, as a metric space, each ball of radius smaller than g/2 in G is isometric to such a tree, whose root is the center of the ball). As long as T < g/2, each step of the random walk {Z_{t}}_{t=0}^{T} moves away from Z_{0} with probability at least \frac{k−1}{k} (if Z_{t} = Z_{0} then this probability is 1) and towards it with probability at most \frac{1}{k}. In other words, as long as T < g/2, the random walk has a positive drift away from Z_{0}. To quantify this, for every 1 < T < g/2 we have:

𝔼 d_{G}(Z_{T} , Z_{0}) ≥ \frac{k − 1}{k}(𝔼 d_{G}(Z_{T −1}, Z_{0}) + 1) + \frac{1}{k} (𝔼 d_{G}(Z_{T −1}, Z_{0}) − 1) = 𝔼 d_{G}(Z_{T −1}, Z_{0}) + \frac{k − 2}{k}.

Hence, for every T < g/2:

𝔼 d_{G}^{2}(Z_{T} , Z_{0}) ≥ (𝔼 d_{G}(Z_{T} , Z_{0}))^{2} ≥ (\frac{k − 2}{k})^{2} T^{2}.

On the other hand:

𝔼 d_{G}^{2}(Z_{T} , Z_{0}) ≤ M_{2}(G)^{2}T 𝔼 d_{G}^{2}(Z_{1}, Z_{0}) = M_{2}(G)^{2}T.

The proposition follows by taking T = ⌈\frac{g}{2} − 1⌉ .

3 Bounding the distortion via Poincaré inequalities

In what follows G is a k regular graph with girth g.

Semi-Definite Programming has proved to be a central tool in establishing lower bounds on c_{2}(·). Our proof of Theorems 1.1 and 1.2, and our second proof of Theorem 1.3 are all based on this point of view, together with an analysis of the algebraic properties of the graphs in question. We first present the necessary background.

Let P SD_{n} be the cone of positive semi-definite symmetric n × n matrices. Define B_{n} to be {Q ∈ P SD_{n}|Q1 = 0}, and let

δ(Q, d) = (\frac{∑_{i,j:Q_{i,j}>0} d^{2}(i, j)Q_{i,j}}{∑_{i,j:Q_{i,j}<0} d^{2}(i, j)|Q_{i,j}|})^{\frac{1}{2}} ,

if the denominator is not 0, and 1 otherwise.

The following lemma gives a formula for c_{2}.

Proposition 3.1: (Linial, London, Rabinovich [11]) Suppose X is finite, |X| = n, then

c_{2}(X, d) = sup_{Q∈B_{n}} δ(Q, d)

In order to make use of the algebraic properties of G, we turn to some background on the following very useful concept.

3.1 Geronimus Polynomials

Let G be a k-regular graph with girth g and let A be its adjacency matrix. We define A^{(t)} as G’s distance t matrix. Namely, A_{i,j}^{(t)} = 1 if the distance d_{G}(i, j) = t and 0 otherwise.

There exist polynomials P_{t}, such that P_{t} has degree t and P_{t}(A) = A^{(t)} for every t < g/2. The conditions that define these polynomials easily translate to a simple recurrence relation. Clearly P_{0}(x) = 1, and P_{1}(x) = x. Note that A^{(t)} − A · A^{(t−1)} equals −kA^{(t−2)} = −k · I for t = 2, and −(k − 1)A^{(t−2)} for 2 < t < g/2. Therefore,

P_{2}(x) = xP_{1}(x) − kP_{0}(x) = x^{2} − k,

and

P_{t}(x) = xP_{t−1}(x) − (k − 1)P_{t−2}(x) for every t > 2.

These polynomials are often called in the literature “Geronimus Polynomials”, a name that we adopt. Basic facts about Geronimus polynomials can be found in [3, 18] (but note the different normalization used in these references). To make this discussion self contained, we briefly review some of the necessary facts and sketch their proofs.

In order to understand the analytical properties of the Geronimus polynomials, one first solves the recursion and finds an explicit formula for them. The following trigonometric expression is obtained:

∀t > 0 P_{t}(2\sqrt{k − 1} cos θ) = (k − 1)^{t/2−1} \frac{(k − 1) sin((t + 1)θ) − sin((t − 1)θ)}{sin θ} (1)

To verify this identity, check the cases t = 1, 2 and note that for t > 2 the recursion relation holds.

Our next observation is that all the roots of P_{t} are real and they all lie between −2\sqrt{k − 1} and 2\sqrt{k − 1}. This can be derived from the general theory of orthogonal polynomials (e.g. [19]), but we provide a direct proof. By identity 1 it suffices to show there are t distinct real values of θ in [0, π) for which the above expression vanishes. Indeed, define θ_{q} = (\frac{π}{2} + qπ)/(t + 1) for q = 0, 1 …, t − 1. Now, it is not hard to see that P_{t}(2\sqrt{k − 1} cos θ_{q}) is positive for even q, and negative for q odd. Therefore, there is a zero for some value of θ between θ_{q} and θ_{q+1}, yielding t zeros in the desired interval.

The last two facts that we need are easily verified by induction:

P_{t}(k) = k(k − 1)^{t−1} ∀t > 0,

and

P′_{t}(k) = \frac{1}{(k − 2)^{2}} (t(k − 1)^{t+1} − 2(k − 1)^{t} − t(k − 1)^{t−1} + 2).

3.2 Technical lemmas

Even though the Geronimus polynomials are not convex throughout [−k, k], we now prove an inequality that reflects the fact that their non-convexity is restricted to the relatively small range [−2\sqrt{k − 1}, 2\sqrt{k − 1}]. The proof uses the classical Markov inequality (see [4]): ∥P′∥_{L_{∞}[−1,1]} ≤ n^{2}∥P ∥_{L_{∞}[−1,1]} for every real polynomial P of degree n, where ∥f∥_{L_{∞}[−a,a]} = sup_{|x|≤a} |f(x)|. A more direct proof can be given by differentiating formula 1, but use of Markov’s inequality eliminates a tedious calculation which leads, essentially, to the same estimate.

Lemma 3.2: Let s ≥ 40 be an even integer. For every ϵ > 0 and x ∈ [−k, k − ϵ],

\frac{P_{s}(k) − P_{s}(k − ϵ)}{ϵ} ≥ \frac{P_{s}(k) − P_{s}(x)}{k − x}.

Proof: Define:

f(x) = \frac{P_{s}(k) − P_{s}(x)}{k − x}.

We need to show that f is non-decreasing on [−k, k]. By taking a derivative of the right hand side and expanding, this follows from the claim that for all x ∈ [−k, k],

h(x) := P_{s}(x) + (k − x)P′_{s}(x) ≤ P_{s}(k).

Note that h(k) = P_{s}(k) and, since P_{s} is an even function (for s even), it follows that h(−k) = P_{s}(k) − 2kP′_{s}(k) < P_{s}(k) (since P′_{s}(k) > 0). It is therefore enough to show that h(x_{0}) ≤ P_{s}(k) whenever h′(x_{0}) = 0. Now, h′(x) = (k − x)P′′_{s}(x), so that the zeros of h′ coincide with the zeros of P′′_{s}. Since P_{s} has all its roots in the interval, [−2\sqrt{k − 1}, 2\sqrt{k − 1}], the same holds for P′′_{s}. It therefore suffices to show that h(x) ≤ P_{s}(k) throughout the interval [−2\sqrt{k − 1}, 2\sqrt{k − 1}]. Every point in this interval has the form x = 2\sqrt{k − 1} cos θ for some 0 ≤ θ ≤ π. Using the trigonometric expression 1 we get:

P_{s}(x) = P_{s}(2 cos θ\sqrt{k − 1}) = (k − 1)^{s/2−1} \frac{(k − 1) sin((s + 1)θ) − sin((s − 1)θ)}{sin θ}.

It is easily verified that sin rα ≤ r sin α for α ∈ [0, π) and r ≥ 1. Therefore,

∥P_{s}∥_{L_{∞}[−2\sqrt{k−1},2\sqrt{k−1}]} ≤ (k − 1)^{s/2−1}((k − 1)(s + 1) + (s − 1)).

Markov’s inequality implies that

∥P′_{s}∥_{L_{∞}[−2\sqrt{k−1},2\sqrt{k−1}]} ≤ \frac{s^{2}}{2\sqrt{k − 1}} · ∥P_{s}∥_{L_{∞}[−2\sqrt{k−1},2\sqrt{k−1}]},

so that:

∥h∥_{L_{∞}[−2\sqrt{k−1},2\sqrt{k−1}]} ≤ ∥P_{s}∥_{L_{∞}[−2\sqrt{k−1},2\sqrt{k−1}]} + 2k∥P′_{s}∥_{L_{∞}[−2\sqrt{k−1},2\sqrt{k−1}]} ≤

≤ (k − 1)^{s/2−1}((k − 1)(s + 1) + (s − 1)) (1 + \frac{ks^{2}}{\sqrt{k − 1}}) ≤

≤ k(k − 1)^{s−1} = P_{s}(k).

It is not hard to verify the last inequality for every k ≥ 3 and s ≥ 40.

We need one more fact concerning Geronimus polynomials:

Lemma 3.3: For every integer s and ϵ ≤ k/20,

P_{s}(k − ϵ) ≥ k(k − 1)^{s−1} · e^{−150ϵs/k}.

Proof: Let y_{1}, …, y_{s} be the roots of P_{s}. By the mean value theorem there is some a ∈ (k − ϵ, k) such that:

log [\frac{P_{s}(k)}{P_{s}(k − ϵ)}] = ϵ\frac{P′_{s}(a)}{P_{s}(a)} =

= ϵ · ∑_{i=1}^{s} \frac{1}{a − y_{i}} ≤ \frac{ϵs}{k − ϵ − 2\sqrt{k − 1}} ≤ \frac{150ϵs}{k},

where we have used the facts that y_{1}, …, y_{n} ∈ [−2\sqrt{k − 1}, 2\sqrt{k − 1}], ϵ ≤ k/20 and k ≥ 3. This yields the required result since P_{s}(k) = k(k − 1)^{s−1}.

Corollary 3.4 Let s ≥ 40 be an even integer and 0 < ϵ ≤ k. Then:

1 − \frac{P_{s}(k − ϵ)}{P_{s}(k)} ≤ C(1 − e^{−Cϵs/k}),

for some absolute constant C > 0.

Proof: When ϵ ≤ k/20 this follows from Lemma 3.3. When ϵ > k/20 the right hand side is bounded from below by an absolute constant. The left hand side is at most 2, since the minimum of P_{s} is attained in the interval [−2\sqrt{k − 1}, 2\sqrt{k − 1}], and the bound obtained in the proof of Lemma 3.2 implies in particular that P_{s}(x) ≥ −P_{s}(k) for every x in this interval.

3.3 Proof of Theorems 1.1 and 1.2

Let G be a k-regular graph with girth g and fix an integer 1 < s < g/2. For every two vertices u, v ∈ V (G) such that d_{G}(u, v) = s there is a unique path of length s joining u and v. In other words, there is a unique set of vertices {w_{u,v}(i)}_{i=0}^{s} ⊂ V (G) such that w_{u,v}(0) = u, w_{u,v}(s) = v and for every i ≥ 1, [w_{u,v}(i − 1), w_{u,v}(i)] ∈ E(G). Each edge e ∈ E(G) appears in exactly s(k − 1)^{s−1} such paths. Hence, for every metric space (X, d_{X}) and every mapping f : V (G) → X

∑_{d_{G}(u,v)=s} d_{X}^{2}(f(u), f(v)) ≤ ∑_{d_{G}(u,v)=s} (∑_{i=1}^{s} d_{X}(f(w_{u,v}(i − 1)), f(w_{u,v}(i))))^{2} ≤

≤ ∑_{d_{G}(u,v)=s} s ∑_{i=1}^{s} d_{X}^{2}(f(w_{u,v}(i − 1)), f(w_{u,v}(i))) = s^{2}(k − 1)^{s−1} ∑_{[u,v]∈E(G)} d_{X}^{2}(f(u), f(v)).

It follows that the inequalities of Theorems 1.1 and 1.2 are trivially true for bounded s, so that we may clearly assume that s ≥ 40. By a similar argument, we can also assume that s is even. In addition, in both statements it is clearly enough to assume that f maps G into H = ℝ.

We begin with the the proof of Theorem 1.2. Let G satisfy the conditions of Theorem 1.2 and consider the following matrix:

Q = αI − A + βA^{(s)},

where 40 ≤ s < g/2 is an even integer, and:

α = k − \frac{ϵP_{s}(k)}{P_{s}(k) − P_{s}(k − ϵ)},

β = \frac{ϵ}{P_{s}(k) − P_{s}(k − ϵ)}.

We claim that Q ∈ B_{n}. Now, Q is clearly symmetric. Also, since A1 = k1, A^{(s)}1 = P_{s}(k)1 so that Q1 = 0. Other than the eigenvalue k, the spectrum of A is in [−k, k − ϵ], so Q will be shown to be positive semi-definite if for all x ∈ [−k, k − ϵ]

α − x + βP_{s}(x) ≥ 0,

which is precisely the statement of Lemma 3.2.

Now, for every f : V (G) → ℝ we get that:

0 ≤ ⟨Qf, f⟩ =

= α ∑_{u∈V (G)} f(u)^{2} − ∑_{u,v∈V (G)} A_{uv}f(u)f(v) + β ∑_{u,v∈V (G)} A_{uv}^{(s)}f(u)f(v) =

= \frac{1}{2} ∑_{[u,v]∈E(G)} |f(u) − f(v)|^{2} − \frac{β}{2} ∑_{d_{G}(u,v)=s} |f(u) − f(v)|^{2},

where in the last equality we have used the fact that α − k + βP_{s}(k) = 0. Hence:

∑_{d_{G}(u,v)=s} |f(u) − f(v)|^{2} ≤ \frac{1}{β} ∑_{[u,v]∈E(G)} |f(u) − f(v)|^{2} =

= \frac{k(k − 1)^{s−1}}{ϵ} [1 − \frac{P_{s}(k − ϵ)}{P_{s}(k)}] ∑_{[u,v]∈E(G)} |f(u) − f(v)|^{2} ≤

≤ C(k − 1)^{s} · \frac{1 − e^{−Cϵs/k}}{ϵ} ∑_{[u,v]∈E(G)} |f(u) − f(v)|^{2},

where we have used Corollary 3.4.

The proof of Theorem 1.1 runs along the same lines. We return to the above construction and let ϵ → 0. This yields a matrix:

Q̃ = [k − \frac{P_{s}(k)}{P′_{s}(k)}] I − A + \frac{1}{P′_{s}(k)}A^{(s)},

which by continuity is in B_{n} as well. Arguing as above, we get the following inequality:

∑_{d_{G}(u,v)=s} |f(u) − f(v)|^{2} ≤ P′_{s}(k) ∑_{[u,v]∈E(G)} |f(u) − f(v)|^{2} =

= \frac{s(k − 1)^{s+1} − 2(k − 1)^{s} − s(k − 1)^{s−1} + 2}{(k − 2)^{2}} ∑_{[u,v]∈E(G)} |f(u) − f(v)|^{2},

which implies the required result.

3.4 Proof of Theorem 1.3

We now deduce Theorem 1.3 from Theorems 1.1 and 1.2. Let G be a k-regular graph (k ≥ 3) with girth g. Take any embedding f : V (G) → ℓ_{2} such that for every u, v ∈ V (G)

\frac{1}{D} ≤ \frac{∥f(u) − f(v)∥}{d_{G}(u, v)} ≤ 1.

Set s = [g/2] − 1. Since there are k(k − 1)^{s−1} vertices of distance s from a fixed vertex we get that:

∑_{d_{G}(u,v)=s} ∥f(u) − f(v)∥^{2} ≥ \frac{s^{2}k(k − 1)^{s−1}|V (G)|}{D^{2}},

and

∑_{[u,v]∈E(G)} ∥f(u) − f(v)∥^{2} ≤ k|V (G)|.

Theorem 1.1 now gives that:

\frac{s^{2}k(k − 1)^{s−1}|V (G)|}{D^{2}} ≤ Cs(k − 1)^{s}|V (G)|,

so that c_{2}(G) ≥ c′\sqrt{g}. If in addition we assume that G has a spectral gap ϵ, this reasoning gives:

c_{2}(G) ≥ c′g\sqrt{\frac{ϵ/k}{1 − e^{−Cgϵ/k}}} ≥ \frac{c′′g}{\sqrt{min \{g, \frac{k}{ϵ} \}}},

which finishes the proof of Theorem 1.3.

4 The relationship between the two methods

The proof of the Markov type 2 property of Hilbert space in [1], sheds some light on the connection between the two methods. In Proposition 3.1 we seek the matrix Q with maximal δ(Q, d) over all Q ∈ B_{n}. We will show how to view Corollary 2.1 as a restriction of Proposition 3.1, in the sense that only a subset of the matrices in B_{n} can be used for the lower bound.

Let B be the symmetric stochastic transition matrix defining the Markov chain, and let γ ∈ (0, 1). Now define

R = \frac{2γ − 1}{γ}I − B + \frac{(1 − γ)^{2}}{γ} ∑_{l≥0}(γB)^{l}

The spectrum of B clearly determines that of R: If λ is an eigenvalue of B, then \frac{2γ−1}{γ} − λ + \frac{(1−γ)^{2}}{γ(1−γλ)} is an eigenvalue of R. This expression is nonnegative for λ ∈ [−1, 1], and 0 for λ = 1. This clearly means that R ∈ B_{n}. If x_{1}, …, x_{n} are vectors in Hilbert space then,

∑_{i,j} R_{i,j}∥x_{i} − x_{j}∥^{2} ≤ 0,

and so

(1 − γ) ∑_{ij}(∑_{l}(γB)^{l})_{ij}∥x_{i} − x_{j}∥^{2} ≤ γ ∑_{ij} B_{ij}∥x_{i} − x_{j}∥^{2}.

As Ball shows by taking γ = 1 − \frac{1}{m}, this is equivalent to the fact that Hilbert space has Markov type 2. To be more precise, this is the original definition he gives to the metric property “having a Markov type 2”.

Thus the approach via Markov type can be viewed as a specialized version of the semidefinite programming method. This method is incomplete in that not every matrix in B_{n} is attained from the above transformation of symmetric stochastic matrices. This method is still very useful, in that it allows one to draw on geometric and probabilistic intuitions. In contrast, the semi-definite approach greatly depends on successful clever guesses of the matrix Q.

The Poincaré inequality method can also be viewed as a restriction of the family B_{n}. Indeed, if G is a graph and B is any matrix such that B_{uv} = 0 whenever u and v are not neighbors in G, then for any matrix C and α ∈ ℝ, the fact that the matrix αI − B + C is in B_{n} is equivalent to the Poincaré inequality:

∑_{u,v∈V (G)} C_{uv}|f(u) − f(v)|^{2} ≤ ∑_{[u,v]∈E(G)} B_{uv}|f(u) − f(v)|^{2},

for every f : V (G) → ℝ. Thus, all the existing lower bounds for c_{2}(·) are based on the study of the above subset of B_{n}, which leads to geometrically intuitive, Poincaré inequality reasons for non-embeddability of graphs in Hilbert space. Hence, in a sense, the full strength of Proposition 3.1 is yet to be fully exploited.

The second part of Theorem 1.3 cannot be derived from Markov type considerations. Indeed, let G be any graph. If {Z_{k}}_{k=0}^{∞} is a symmetric Markov chain on G such that P (Z_{k+1} = u|Z_{k} = u) = 0 for every u ∈ V (G) then clearly 𝔼 d_{G}^{2}(Z_{T} , Z_{0}) ≤ diam(G)^{2}𝔼 d_{G}^{2}(Z_{1}, Z_{0}) and by the triangle inequality 𝔼 d_{G}^{2}(Z_{T} , Z_{0}) ≤ T^{2}𝔼 d_{G}^{2}(Z_{1}, Z_{0}). Hence, for every T,

M_{2}(G) ≤ min \{\frac{diam(G)}{\sqrt{T}}, T \} ,

which implies that M_{2}(G) = O(diam(G)^{2/3}), while our second proof of Theorem 1.3 showed that there are graphs with c_{2}(G) = Ω(diam(G)).

An interesting problem that still remains open is the determination of the worst possible behavior of c_{2}(G) over all k-regular, k ≥ 3, graphs with girth g. Our present methods seem to break at \sqrt{g}. On the other hand if k-regular graphs, G, with girth g and c_{2}(G) = O(\sqrt{g}) exist, they cannot be expanders in view of the known lower bound for the Euclidean distortion of expanders. This observation rules out most known constructions for graphs with large girth. Although examples of k-regular graphs with large girth which are not expanders are known, these specific examples seem highly complicated and far from Euclidean.

Another problem worth mentioning is whether the lower bound for c_{2}(G) still holds without the regularity assumptions, i.e. if we only assume that the graph has large girth and the degree of each vertex is greater than 2. Finally, it would be very interesting to find lower bounds for c_{1}(G) as a function of the girth of G. In particular, we do not know if c_{1}(G) must tend to infinity when g → ∞.

References

[1] K. Ball, Markov Chains, Riesz Transforms and Lipschitz Maps, Geometric and Functional Analysis 2, p. 137-172 (1992).

[2] Y. Bartal, On approximating arbitrary metrics by tree metrics. In STOC ’98 (Dallas, TX), pages 161-168. ACM, New York, 1998. Proc. of the 24th International Colloquium on Automata, Languages, and Programming, July 1997.

[3] Biggs, Algebraic graph theory p. 182. Cambridge University Press, Cambridge, second edition (1993).

[4] P. Borwein and T. Erdélyi, Polynomials and polynomial inequalities, Graduate Texts in Mathematics, 161. Springer-Verlag, New York, 1995.

[5] J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52, p. 46-52, (1985).

[6] J. Bourgain, The metrical interpretation of superreflexivity in Banach spaces, Israel J. Math. p. 56 p. 222 - 230 (1986).

[7] J. Bourgain, V. Milman, H. Wolfson, On type of metric spaces, Trans. Amer. Math. Soc. 294 p. 295-317 (1986).

[8] P. Enflo, On the nonexistence of uniform homeomorphisms between L_{p}-spaces, Arkiv För Matematik, 8(1969), 103-105.

[9] A. Gupta, I. Newman, Y. Rabinovich and A. Sinclair, Cuts, Trees and ℓ_{1}-Embeddings of Graphs. In Symposium on Foundations of Computer Science (1999).

[10] P. Klein, S.A. Plotkin and S.B. Rao, Excluded minors, network decomposition and multicommodity flow. In 25th Annual ACM Symposium on the Theory of Computing, p. 682-690 (1993).

[11] N. Linial, E. London and Yu. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica, 15 p. 215 - 245 (1995).

[12] N. Linial and M. Saks, On the Euclidean distortion of complete binary trees, preprint.

[13] N. Linial and A. Magen, Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders, J. of Combinatorial Theory ser. B, 79 p. 157-171 (2000).

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

[15] J. Matoušek, On embedding trees into uniformly convex Banach spaces, Israel J. Math. 114 p. 221-237 (1999).

[16] G. Pisier, Probabilistic methods in the geometry of Banach spaces, Probability and Analysis (Varena, Italy, 1985), Lecture notes in Math., 1206, Springer-Verlag, 167-241.

[17] S.B. Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics. In 15th Annual ACM Symposium on Computational Geometry, p. 300-306 (1999).

[18] P. Solé, The Second Eigenvalue of Regular Graphs of Given Girth, J. Combinatorial Theory, Ser. B 56, p. 239-249 (1992).

[19] Szegõ, G., Orthogonal polynomials. Fourth edition. American Mathematical Society, Colloquium Publications, Vol. XXIII. American Mathematical Society, Providence, R.I., 1975.

[20] M. Talagrand, Isoperimitry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem. GAFA 3 (1993), 295-314.

[21] R. Wagner, Notes on an inequality by Pisier for Functions on the Discrete Cube, Geometric Aspects of Functional Analysis, Lecture Notes in Math. 1745, 263-268, Springer-Verlag, Berlin, 2000.