.

TOWARDS A CALCULUS FOR NON-LINEAR SPECTRAL GAPS

[EXTENDED ABSTRACT]

MANOR MENDEL AND ASSAF NAOR

Abstract. Given a finite regular graph G = (V, E) and a metric space (X, d_{X}), let γ_{+}(G, X) denote the smallest constant γ_{+} > 0 such that for all f, g : V → X we have:

\frac{1}{|V |^{2}} ∑_{x,y∈V} d_{X}(f(x), g(y))^{2} ⩽ \frac{γ_{+}}{|E|} ∑_{xy∈E} d_{X}(f(x), g(y))^{2}.

In the special case X = ℝ this quantity coincides with the reciprocal of the absolute spectral gap of G, but for other geometries the parameter γ_{+}(G, X), which we still think of as measuring the non-linear spectral gap of G with respect to X (even though there is no actual spectrum present here), can behave very differently.

Non-linear spectral gaps arise often in the theory of metric embeddings, and in the present paper we systematically study the theory of non-linear spectral gaps, partially in order to obtain a combinatorial construction of a super-expander — a sequence of bounded-degree graphs {G_{i} = (V_{i}, E_{i})}_{i=1}^{∞} which does not admit a coarse embedding into any uniformly convex normed space. In addition, the bi-Lipschitz distortion of G_{i} in any uniformly convex normed space is Ω(log |V_{i}|), which is the worst possible behavior due to Bourgain’s embedding theorem [4]. Such remarkable graph families were previously known to exist due to a tour de force algebraic construction of Lafforgue [17]. Our construction is different and combinatorial, relying on the zigzag product of Reingold-Vadhan-Wigderson [38].

We show that non-linear spectral gaps behave sub-multiplicatively under zigzag products — a fact that amounts to a simple iteration of the inequality above. This yields as a special case a very simple (linear algebra free) proof of the Reingold-Vadhan-Wigderson theorem which states that zigzag products preserve the property of having an absolute spectral gap (with quantitative control on the size of the gap). The zigzag iteration of Reingold-Vadhan-Wigderson also involves taking graph powers, which is trivial to analyze in the classical “linear” setting. In our work, the behavior of non-linear spectral gaps under graph powers becomes a major geometric obstacle, and we show that for uniformly convex normed spaces there exists a satisfactory substitute for spectral calculus which makes sense in the non-linear setting. These facts, in conjunction with a variant of Ball’s notion of Markov cotype and a Fourier analytic proof of the existence of appropriate “base graphs”, are shown to imply that Reingold-Vadhan-Wigderson type constructions can be carried out in the non-linear setting.

2010 Mathematics Subject Classification. 51F99,05C12,05C50,46B85. To be published (in a different layout) in the proceedings of the ACM-SIAM Symposium on Discrete

Algorithms 2010 (SODA ’10).

1. Introduction

Let A = (a_{ij}) be an n × n symmetric stochastic matrix and let

1 = λ_{1}(A) ⩾ λ_{2}(A) ⩾ ⋯ ⩾ λ_{n}(A) ⩾ −1

be its eigenvalues. The reciprocal of the spectral gap of A, i.e., the quantity \frac{1}{1−λ_{2}(A)}, is the smallest constant γ > 0 such that for every x_{1}, …, x_{n} ∈ ℝ we have

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n}(x_{i} − x_{j})^{2} ⩽ \frac{γ}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}(x_{i} − x_{j})^{2}.  (1)

By summing over the coordinates with respect to some orthonormal basis, (1) can be restated as follows: the value \frac{1}{1−λ_{2}(A)} is the smallest constant γ > 0 such that for all x_{1}, …, x_{n} ∈ L_{2} we have

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{2}^{2} ⩽ \frac{γ}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥_{2}^{2}.  (2)

Once one realizes the validity of inequality (2) it is natural to generalize it in several ways. For example, we can replace the exponent 2 by some other exponent p > 0 and, more crucially, we can replace the Euclidean geometry by some other metric space (X, d). Such generalizations are standard practice in metric geometry, as we shall discuss below. For the sake of presentation, we can take this generalization to even greater extremes: let X be an arbitrary set and let K : X × X → [0, ∞) be a symmetric function. Such functions are often called kernels in the literature, and we shall adopt this terminology here. Define the reciprocal spectral gap of A with respect to K, denoted γ(A, K), as the infimum over all γ ⩾ 0 such that for all x_{1}, …, x_{n} ∈ X we have

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} K(x_{i}, x_{j}) ⩽ \frac{γ}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}K(x_{i}, x_{j}).  (3)

In what follows we will also call γ(A, K) the Poincaré constant of A with respect to K. Readers are encouraged to focus on the case when K is a power of some metric on X, though as will become clear presently, a surprising amount of ground can be covered without any assumption on the kernel K. For concreteness we restate the above discussion: the standard gap in the linear spectrum of A corresponds to considering Poincaré constants with respect to Euclidean spaces (i.e., kernels which are squares of Euclidean metrics), but there is scope for a theory of non-linear spectral gaps when one considers inequalities such as (3) with respect to other geometries. The purpose of this paper is to make some steps towards such a theory, with emphasis on possible extensions of spectral calculus to non-linear (non-Euclidean) settings. We apply our new calculus for non-linear spectral gaps to construct new strong types of expanders, and to resolve a question of Lafforgue [17]. We obtain a new combinatorial construction of a remarkable type of bounded degree graphs whose shortest path metric is incompatible with the geometry of any uniformly convex normed space in a very strong sense (i.e., coarse non-embeddability). The existence of such graph families was first discovered by Lafforgue [17] via an algebraic construction. Our work indicates that there is hope for a useful theory of non-linear spectral gaps, beyond the sporadic examples that have been previously studied in the literature.

1.1. Coarse non-embeddability. A sequence of metric spaces {(X_{n}, d_{n})}_{n=1}^{∞} is said to embed coarsely (with uniform moduli) into a metric space (Y, d_{Y}) if there exist two nondecreasing functions α, β : [0, ∞) → [0, ∞) such that lim_{t→∞} α(t) = ∞, and mappings f_{n} : X_{n} → Y, such that for all n ∈ ℕ and x, y ∈ X_{n} we have:

α (d_{X_{n}}(x, y)) ⩽ d_{Y} (f_{n}(x), f_{n}(y)) ⩽ β (d_{X_{n}}(x, y)) .  (4)

Equation (4) should be viewed as a weak form of “metric faithfulness” of the mappings f_{n}: this seemingly humble requirement can be restated informally as “large distances should map uniformly to large distances”. Nevertheless, this weak notion of embedding (which is much weaker than, say, bi-Lipschitz embeddability), has a wide range of applications in geometry and group theory: see for example the book [39] and the references therein for (a small part of) such applications.

Since coarse embeddability is a weak requirement, it is quite difficult to prove coarse nonembeddability: very few methods to establish such a result are known, among which is the use of non-linear spectral gaps, as pioneered by Gromov [10] (other such methods are coarse notions of metric dimension [9], or the use of metric cotype [23]. These methods do not seem to be applicable to the question that we study here). Gromov’s argument is simple: assume that X_{n} = (V_{n}, E_{n}) are regular graphs of bounded degree and that d_{n}(·, ·) is the shortest-path metric on X_{n}. Assume also that for some p, γ ∈ (0, ∞) we have for all n ∈ ℕ and f : V_{n} → Y:

\frac{1}{|V_{n}|^{2}} ∑_{u,v∈V_{n}} d_{Y} (f(u), f(v))^{p} ⩽ \frac{γ}{|E_{n}|} ∑_{x,y∈E_{n}} d_{Y} (f(x), f(y))^{p}.  (5)

A combination of (4) and (5) yields the bound \frac{1}{|V_{n}|^{2}} ∑_{u,v∈V_{n}} α (d_{n}(u, v))^{p} ⩽ γβ(1)^{p}. But, since X_{n} is a bounded degree graph, at least half of the pairs of vertices u, v ∈ V_{n} satisfy d_{n}(u, v) ⩾ c log |V_{n}|, where c is a constant which depends on the implied degree bound (but not on n). Thus α(c log |V_{n}|)^{p} ⩽ 2γβ(1)^{p}, and in particular if lim_{n→∞} |V_{n}| = ∞ then we get a contradiction to the assumption lim_{t→∞} α(t) = ∞. Observe in passing that this argument also shows that X_{n} has bi-Lipschitz distortion Ω(log |V_{n}|) in Y — such an argument was first used by Linial, London and Rabinovich [19] (see also [20]) to show that Bourgain’s embedding theorem [4] is asymptotically sharp.

Assumption (5) can be restated as saying that γ(A_{n}, d_{Y}^{p}) ⩽ γ, where A_{n} is the normalized adjacency matrix of X_{n}. This condition can be viewed to mean that the graphs {X_{n}}_{n=1}^{∞} are “expanders” with respect to (Y, d_{Y}). Note that if Y contains at least two points then (5) implies that {X_{n}}_{n=1}^{∞} are necessarily also expanders in the classical sense.

The key point in the coarse non-embeddability question is therefore to construct such {X_{n}}_{n=1}^{∞} for which we can prove the inequality (5) for non-Hilbertian targets Y. This question has been previously investigated by several authors. Matoušek [20] devised an extrapolation method for Poincaré inequalities (see also the description of Matoušek’s argument in [3]) which establishes the validity of (5) for every expander when Y = L_{p}. The work of Ozawa [30] and Pisier [32, 35] proves (5) for every expander when Y is Banach space which satisfies certain geometric conditions (e.g., Y can be taken to be a Banach lattice with finite cotype). In [28, 27] additional results of this type are obtained.

A normed space is called super-reflexive if it admits an equivalent norm which is uniformly convex. Recall that a normed space (X, ∥·∥_{X}) is called uniformly convex if for every ε ∈ (0, 1) there exists δ = δ_{X}(ε) > 0 such that for any two vectors x, y ∈ X with ∥x∥_{X} = ∥y∥_{X} = 1 and ∥x − y∥_{X} ⩾ ε we have ∥\frac{x+y}{2} ∥_{X} ⩽ 1 − δ (thus uniform convexity is a uniform version of strict convexity). The question whether there exists a sequence of arbitrarily large graphs of bounded degree which do not admit a coarse embedding into any super-reflexive normed space was posed by Kasparov and Yu in [15], and was solved in the remarkable work of Lafforgue [17] on the strengthened version of property (T) for SL_{3}(𝔽) when 𝔽 is a non-Archimedian local field (thus, for concreteness, Lafforgue’s graphs can be obtained as Cayley graphs of finite quotients of co-compact lattices in SL_{3}(ℚ_{p}), where p is a prime and ℚ_{p} is the p-adic rationals).

In this paper we obtain an alternative solution of the Kasparov-Yu problem using a combinatorial construction based on the “zigzag expanders” of Reingold, Vadhan, and Wigderson [38]. More specifically, we construct a family of 9-regular graphs which satisfies (5) for every super-reflexive Banach space X (where γ depends only on X) — such graphs are called super-expanders.

We state at the outset that it is a major open question whether every expander satisfies (5) for every uniformly convex normed space X. It is also unknown whether there exist graph families of bounded degree and logarithmic girth which do not admit a coarse embedding into any super-reflexive normed space—this question is of particular interest in the context of the potential application to the Novikov conjecture that was suggested by Kasparov and Yu in [15]. Note that some geometric restriction on the target space X must be imposed, since the relation between non-linear spectral gaps and coarse non-embeddability, in conjunction with the fact that every finite metric space embeds isometrically into ℓ_{∞}, shows that (for example) X = ℓ_{∞} can never satisfy (5) for bounded degree family of graphs.

Our combinatorial approach can be used to show that there exist bounded degree graph sequences which do not admit a coarse embedding into any K-convex normed space. A normed space X is K-convex^{1} if there exists ε_{0} > 0 and n_{0} ∈ ℕ such that any embedding of ℓ_{1}^{n_{0}} into X incurs distortion at least 1+ε_{0}, see [33]. This question was asked by Lafforgue [17]. Recently, independently of our work, Lafforgue [18] managed to modify his argument to obtain coarse non-embeddability into K-convex spaces for his graph sequences as well.

Acknowledgments. Michael Langberg was involved in early discussions on the analysis of the zigzag product. Keith Ball helped in simplifying this analysis. M. M. was partially supported by ISF grant no. 221/07, BSF grant no. 2006009, and a gift from Cisco research center. A. N. was supported in part by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

2. A combinatorial approach to the existence of Super-Expanders

2.1. The compatibility of non-linear spectral gaps with combinatorial constructions. The parameter γ(A, K) will reappear presently, but for the purpose of this section we need to study a variant of it which corresponds to the absolute spectral gap of a matrix (similar to the role of absolute spectral gaps in the work of Reingold-Vadhan-Wigderson [38]). Define λ(A) = max_{2⩽i⩽n} |λ_{i}(A)| and call the quantity 1 − λ(A) the absolute spectral gap of A. Similarly to (2), the reciprocal of the absolute spectral gap of A is the smallest constant γ_{+} > 0 such that for all x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ L_{2} we have

1K-convexity is also equivalent to X having type strictly bigger than 1, see [25, 21]. The K-convexity property is strictly weaker than super-reflexivity, see [12, 14, 13, 36].

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − y_{j}∥_{2}^{2} ⩽ \frac{γ_{+}}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − y_{j}∥_{2}^{2}.  (6)

Analogously to (3), given a kernel K : X × X → [0, ∞) we can then define γ_{+}(A, K) to be the the infimum over all γ_{+} ⩾ 0 such that for all x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ X we have

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} K(x_{i}, y_{j}) ⩽ \frac{γ_{+}}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}K(x_{i}, y_{j}).  (7)

Note that clearly γ_{+}(A, K) ⩾ γ(A, K).

In what follows we will often deal with regular graphs, which will always be allowed to have self loops and multiple edges. We will use the convention that each self loop contribute 1 to the degree of a vertex. The normalized adjacency matrix of a d-regular graph G = (V, E), denoted A_{G}, is defined as usual by letting its u, v entry be the number of edges joining u, v ∈ V divided by d. When discussing Poincaré constants we will interchangeably identify G with A_{G}. Thus, for example, we write γ_{+}(G, K) = γ_{+}(A_{G}, K).

The starting point of our work is an investigation of the behavior of the quantity γ_{+}(G, K) under certain graph operations, the most important of which (for our purposes) is the zigzag product of Reingold-Vadhan-Wigderson [38]. As we shall see below, combinatorial constructions seem to be well-adapted to controlling non-linear quantities such as γ_{+}(G, K). This crucial fact allows us to use them in a perhaps unexpected geometric context.

Assume now that G_{1} = (V_{1}, E_{1}) is an n_{1}-vertex graph which is d_{1}-regular and that G_{2} = (V_{2}, E_{2}) is a d_{1}-vertex graph which is d_{2}-regular. Since the number of vertices in G_{2} is the same as the degree in G_{1}, we can identify V_{2} with the edges emanating from a given vertex u ∈ V_{1}. Formally, we fix for every u ∈ V_{1} a bijection π_{u} : {e ∈ E_{1} : u ∈ e} → V_{2}. Moreover, we fix for every a ∈ V_{2} a bijection between [d_{2}] = {1, …, d_{2}} and the multiset of the vertices adjacent to a in G_{2}, κ_{a} : [d_{2}] → {b ∈ V_{2} : {a, b} ∈ E_{2}}.

The zigzag product G_{1} ◯ z G_{2} is the graph whose vertices are V_{1} × V_{2} and (u, a), (v, b) ∈ V_{1} × V_{2} are joined by an edge if and only if there exist i, j ∈ [d_{2}] such that:

{u, v} ∈ E_{1} and a = κ_{π_{u}({u,v})}(i) and b = κ_{π_{v}({u,v})}(j).

The schematic description of this construction is as follows: think of the vertex set of G_{1}◯ z G_{2} as a disjoint union of “clouds” which are copies of V_{2} = {1, …, d_{1}} indexed by V_{1}. Thus (u, a) is the point indexed by a in the cloud labeled by u. Every edge {(u, a), (v, b)} of G_{1} ◯ z G_{2} is the result of a three step walk: a “zig” step in G_{2} from a to π_{u}({u, v}) in u’s cloud, a “zag” step in G_{1} from u’s cloud to v’s cloud along the edge {u, v} and a final “zig” step in G_{2} from π_{v}({u, v}) to b in v’s cloud. The zigzag product is illustrated in Figure 1. The number of vertices of G_{1} ◯ z G_{2} is n_{1}d_{1} and its degree is d_{2}^{2}.

The zigzag product depends on the labels {π_{u}}_{u∈V_{1}},and in fact different labels of the same graphs can produce non-isomorphic products^{2}. However, all of our results below will be independent of the actual choice of the labeling, so while our notation should formally depend on the labeling, we will drop its explicit mention for the sake of simplicity.

2The labels {κ_{a}}_{a∈V_{2}} do not affect the structure of the zigzag product but they are useful in the subsequent analysis.

Figure 1. Illustration of the zigzag product. The upper part of the figure depicts part of a 4-regular graph G_{1}, and a 4-vertex cycle G_{2}. The bottom part of the figure depicts the edges of the zigzag product between u’s cloud and v’s cloud. The original edges of G_{1} and G_{2} are drawn as dotted and dashed lines (respectively).

Let us now examine how γ_{+}(G_{1} ◯ z G_{2}, K) is related to γ_{+}(G_{1}, K), and γ_{+}(G_{2}, K), where K : X × X → [0, ∞) is an arbitrary kernel. To this end take f, g : V_{1} × V_{2} → X and note that the definition of γ_{+}(G_{1}, K) implies that for all a, b ∈ V_{2} we have:

\frac{1}{n_{1}^{2}} ∑_{u,v∈V_{1}} K (f(u, a), g(v, b)) ⩽ \frac{γ_{+}(G_{1}, K)}{n_{1}d_{1}} ∑_{\{u,v\}∈E_{1}} K (f(u, a), g (v, b)) .  (8)

Thus:

\frac{1}{|V_{1} × V_{2}|^{2}} ∑_{(u,a),(v,b)∈V_{1}×V_{2}} K(f(u, a), g(v, b)) = \frac{1}{d_{1}^{2}} ∑_{a,b∈V_{2}} \frac{1}{n_{1}^{2}} ∑_{u,v∈V_{2}} K(f(u, a), g(v, b))

⩽^{(8)} \frac{γ_{+}(G_{1}, K)}{n_{1}d_{1}^{3}} ∑_{a,b∈V_{2}} ∑_{\{u,v\}∈E_{1}} K (f(u, a), g (v, b)) . (9)

Next, the definition of γ_{+}(G_{2}, K) implies that for all u ∈ V_{1} and b ∈ V_{2} we have

\frac{1}{d_{1}^{2}} ∑_{a∈V_{2}} ∑_{\begin{matrix}v∈V_{1}: \\ \{u,v\}∈E_{1} \end{matrix}} K (f(u, a), g (v, b))

⩽ \frac{γ_{+}(G_{2}, K)}{d_{1}d_{2}} ∑_{\begin{matrix}v∈V_{1}: \\ \{u,v\}∈E_{1} \end{matrix}} ∑_{i∈[d_{2}]} K (f (u, κ_{π_{u}(\{u,v\})}(i)) , g (v, b)) . (10)

Summing (10) over u ∈ V_{1} and b ∈ V_{2} and plugging it into (9), yields the bound:

\frac{1}{|V_{1} × V_{2}|^{2}} ∑_{(u,a),(v,b)∈V_{1}×V_{2}} K(f(u, a), g(v, b))

⩽ \frac{γ_{+}(G_{1}, K)γ_{+}(G_{2}, K)}{n_{1}d_{1}^{2}d_{2}} ∑_{v∈V_{1}} ∑_{i∈[d_{2}]} ∑_{\begin{matrix}u∈V_{1}: \\ \{u,v\}∈E_{1} \end{matrix}} ∑_{b∈V_{2}} K (f (u, κ_{π_{u}(\{u,v\})}(i)) , g (v, b)) . (11)

Another application of the definition of γ_{+}(G_{2}, K) implies that for all v ∈ V_{1} and i ∈ [d_{2}] we have:

\frac{1}{d_{1}^{2}} ∑_{\begin{matrix}u∈V_{1}: \\ \{u,v\}∈E_{1} \end{matrix}} ∑_{b∈V_{2}} K (f (u, κ_{π_{u}(\{u,v\})}(i)) , g (v, b))

⩽ \frac{γ_{+}(G_{2}, K)}{d_{1}d_{2}} ∑_{\begin{matrix}u∈V_{1}: \\ \{u,v\}∈E_{1} \end{matrix}} ∑_{j∈[d_{2}]} K (f (u, κ_{π_{u}(\{u,v\})}(i)) , g (v, κ_{π_{v}(\{u,v\})}(j))) . (12)

Summing (12) over v ∈ V_{1} and i ∈ [d_{2}] and combining the resulting inequality with (11) yields the bound:

\frac{1}{|V_{1} × V_{2}|^{2}} ∑_{(u,a),(v,b)∈V_{1}×V_{2}} K(f(u, a), g(v, b))

⩽ \frac{γ_{+}(G_{1}, K)γ_{+}(G_{2}, K)^{2}}{n_{1}d_{1}d_{2}^{2}} ∑_{\{u,v\}∈E_{1}} ∑_{i,j∈[d_{2}]} K (f (u, κ_{π_{u}(\{u,v\})}(i)) , g (v, κ_{π_{v}(\{u,v\})}(j)))

= \frac{γ_{+}(G_{1}, K)γ_{+}(G_{2}, K)^{2}}{n_{1}d_{1}d_{2}^{2}} ∑_{\{(u,a),(v,b)\}∈E(G_{1}◯ z G_{2})} K (f (u, a) , g (v, b)) .

Hence we deduce the following theorem:

Theorem 1 (Sub-multiplicativity). Let G_{1} = (V_{1}, E_{1}) be an n_{1}-vertex graph which is d_{1}- regular and let G_{2} = (V_{2}, E_{2}) be a d_{1}-vertex graph which is d_{2}-regular. Then for every every kernel K : X × X → [0, ∞),

γ_{+} (G_{1} ◯ z G_{2}, K) ⩽ γ_{+}(G_{1}, K) · γ_{+}(G_{2}, K)^{2}.

In the special case X = ℝ and K(x, y) = (x − y)^{2}, Theorem 1 becomes:

\frac{1}{1 − λ(G_{1} ◯ z G_{2})} ⩽ \frac{1}{1 − λ(G_{1})} · \frac{1}{(1 − λ(G_{2}))^{2}} .  (13)

Thus λ(G_{1} ◯ z G_{2}) ⩽ f(λ(G_{1}), λ(G_{2})) where f(λ_{1}, λ_{2}) < 1 when λ_{1}, λ_{2} ∈ (0, 1). This is the main result of Reingold-Vadhan-Wigderson [38], and it coincides with the later bound of Reingold-Trevisan-Vadhan [37]. We note that in [38] an improved bound for λ(G_{1} ◯ z G_{2}) is obtained which is better than the bound of [37] (and hence also (13)), though this improvement has not been used (so far) in the literature. Theorem 1 shows that the fact that zigzag products preserve spectral gaps has nothing to do with the underlying Euclidean geometry (or linear algebra) that was used in [38, 37]: this is a truly non-linear phenomenon which holds in much greater generality, and simply amounts to an iteration of the Poincaré inequality (7). In the full version of this paper we present versions of the sub-multiplicativity result in Theorem 1 for other types of graph products such as tensor products, replacement products [8, 38], balanced replacement products [38], and derandomized square [40].

2.2. An iterative construction of super-expanders. Let us briefly recall how the Euclidean case of Theorem 1 was used by Reingold-Vadhan-Wigderson [38] to construct expanders (see also the nice exposition in Section 9.2 of the survey [11]).

For a graph G = (V, E) and for t ∈ ℕ, let G^{t} be the graph in which an edge between u, v ∈ V is drawn for every walk in G of length t whose endpoints are u, v. Thus A_{G^{t}} = (A_{G})^{t} and if G is d-regular then G^{t} is d^{t}-regular.

Let H be an arbitrary regular graph with n_{0} vertices and degree d_{0}. Such a graph H will be called the base graph in what follows. Fix t_{0} ∈ ℕ. Define G_{1} = H^{2} and inductively G_{i+1} = G_{i}^{t_{0}} ◯ z H (in [38] it sufficed to take t_{0} = 2, but we will quickly realize that in the nonlinear setting we need to work with higher powers, which is the reason why we are stating the construction for general t_{0}). For this construction to be feasible we need to ensure that n_{0} = d_{0}^{2t_{0}}, since in that case for all i ∈ ℕ the graph G_{i} is well defined and has n_{0}^{i} = d_{0}^{2it_{0}} vertices and degree d_{0}^{2}. Using the fact that λ(G^{t_{0}}) = λ(G)^{t_{0}}, we see that λ(G_{1}) = λ(H)^{2} and it follows from (13) that for i ∈ ℕ we have λ(G_{i+1}) ⩽ 1 − (1 − λ(G_{i})^{t_{0}}) (1 − λ(H))^{2}. We thus see inductively that if λ(H) ⩽ 1 − (2 − 2^{1−t_{0}})^{−1/2} then λ(G_{i}) ⩽ \frac{1}{2} for all i ∈ ℕ.

Given Theorem 1, the above scheme suggests that we can repeat the Reingold-Vadhan-Wigderson iteration for every kernel K for which a sufficiently good base graph H exists. There is, however, an obstacle to this approach: we used above the identity λ(A^{t}) = λ(A)^{t} (t ∈ ℕ) in order to increase the spectral gap of G_{i} in each step of the iteration. While this identity is a trivial corollary of spectral calculus, and was thus the “trivial part” of the construction in [38], there is no reason to expect that γ_{+}(A^{t}, K) decreases similarly with t for other kernels K : X × X → [0, ∞). To better grasp what is happening here let us examine the asymptotic behavior of γ_{+}(A^{t}, | · |^{2}) as a function of t (here and in what follows | · | denotes the absolute value on ℝ):

γ_{+} (A^{t}, | · |^{2}) = \frac{1}{1 − λ(A^{t})} = \frac{1}{1 − λ(A)^{t}}

= \frac{1}{1 − (1 − \frac{1}{γ_{+}(A,|·|^{2})})^{t}} ≍ max \{1, \frac{γ_{+} (A, | · |^{2})}{t}\} , (14)

where above, and in what follows, ≍ denotes equivalence up to universal constants (we will also use the notation ≲, ≳ to express the corresponding inequalities up to universal constants). Restating (14) in words, raising a matrix to a large power t ∈ ℕ corresponds to decreasing its (real) Poincaré constant by a factor of t as long as it is possible to do so (note that the Poincaré constant is necessarily at least 1).

For our scheme to work for other kernels K : X ×X → [0, ∞) we would like K to satisfy a “spectral calculus” inequality of this type, i.e., an inequality which ensures that, if γ_{+}(A, K) is large, then γ_{+}(A^{t}, K) is much smaller than γ_{+}(A, K) for sufficiently large t ∈ ℕ. This is, in fact, not the case in general: in the Section 3.3 we construct a metric space (X, d_{X}) such that for each n ∈ ℕ there is a symmetric stochastic matrix A_{n} such that γ_{+}(A_{n}, d_{X}^{2}) ⩾ n yet for every t ∈ ℕ there is n_{0} ∈ ℕ such that for all n ⩾ n_{0} we have γ_{+}(A_{n}^{t}, d_{X}^{2}) ⩾ \frac{1}{2}γ_{+}(A_{n}, d_{X}^{2}). The question which metric spaces satisfy the required spectral calculus inequalities thus becomes a subtle issue which we believe is of fundamental importance, beyond the particular application that we present here. A large part of the present paper is devoted to addressing this question. We obtain rather satisfactory results which allow us to carry out a zigzag type construction of super-expanders — expanders with respect to super-reflexive spaces — though we are still quite far from a complete understanding of the behavior of non-linear spectral gaps under graph powers for non-Euclidean geometries.

We will introduce in Section 2.3 a criterion on a metric space (X, d_{X}), which is a bi-Lipschitz invariant, and we prove that it implies that for every n, m ∈ ℕ and every n × n symmetric stochastic matrix A the Cesàro averages \frac{1}{m} ∑_{t=0}^{m−1} A^{t} satisfy the following spectral calculus inequality:

γ_{+} (\frac{1}{m} ∑_{t=0}^{m−1} A^{t}, d_{X}^{2}) ⩽ C(X) max \{1, \frac{γ_{+} (A, d_{X}^{2})}{m^{ε(X)}}\} ,  (15)

where C(X), ε(X) ∈ (0, ∞) depend only on the geometry of X but not on n, m, A. The fact that we can only prove such an inequality for Cesàro averages rather than powers does not create any difficulty in the ensuing argument, as we shall see presently. We postpone the discussion of the metric criterion which implies (15) to Section 2.3. It suffices to say here that we show that certain classes of metric spaces, including super-reflexive normed spaces, satisfy this criterion, and hence also (15).

Note that Cesàro averages have the following combinatorial interpretation in the case of graphs: given an n-vertex d-regular graph G = (V, E) let 𝒜_{m}(G) be the graph whose vertex set is V and for every t ∈ {0, …, m − 1} and u, v ∈ V we draw d^{m−1−t} edges joining u, v for every walk in G of length t which starts at u and terminates at v. With this definition A_{𝒜_{m}(G)} = \frac{1}{m} ∑_{t=0}^{m−1} A_{G}^{t}, and 𝒜_{m}(G) is md^{m−1}-regular. We will slightly abuse this notation by also using the shorthand 𝒜_{m}(A) = \frac{1}{m} ∑_{t=0}^{m−1} A^{t}, when A is a matrix.

Another issue which we must overcome is the existence of a sufficiently good base graph H for our zigzag iteration. This is also a subtle point which is discussed in Section 2.4 below. In order to present our construction here, we first state the following lemma, and postpone the discussion about it to Section 2.4:

Lemma 2.1 (Existence of base graphs). There exists an unbounded increasing sequence of integers {n_{i}}_{i=1}^{∞} satisfying n_{i+1} ⩽ 100n_{i} with the following property: for every δ ∈ (0, 1) there is a sequence of regular graphs {H_{i}(δ)}_{i=1}^{∞} such that H_{i}(δ) has n_{i} vertices and degree d_{i}(δ) ⩽ e^{(log n_{i})^{1−δ}}. Moreover, for every super-reflexive (even just K-convex) normed space (X, ∥ · ∥_{X}) there exist δ_{0}(X), γ(X) ∈ (0, 1) such that for all 0 < δ ⩽ δ_{0}(X) and all i ∈ ℕ, we have γ_{+} (H_{i}(δ), ∥ · ∥_{X}^{2}) ⩽ γ(X).

We briefly discuss a simple operation, called edge completion, which allows us to change the degree of a graph while not changing its Poincaré constant by too much. This operation will generate a lot of freedom in applying zigzag products, since we will be able to apply it in order to adjust the degrees of graphs so that their zigzag product becomes well-defined. Given a d-regular graph G = (V, E) and an integer d′ ⩾ d define the d′-edge completion of G, denoted 𝒞_{d′}(G) = (V, E′), as follows. Writing d′ = ℓd+r where ℓ ∈ ℕ, and r ∈ {0, …, d−1}, duplicate each edge in G ℓ times, and add r self-loops to each vertex of G. This makes 𝒞_{d′}(G) a d′-regular graph. It is evident from the definition of γ_{+}(·, ·) that for every kernel K : X × X → [0, ∞) we have γ_{+} (𝒞_{d′}(G), K) ⩽ 2γ_{+}(G, K).

With these facts at hand, we can now construct an expander with respect to a given super-reflexive Banach space X.

Lemma 2.2. For every super-reflexive Banach space X there exist C′(X) ⩾ 1, d = d(X) ∈ ℕ and sequence of d-regular graphs {F_{j}(X)}_{j=1}^{∞} whose number of vertices tend to ∞ with j, such that γ_{+}(F_{j}(X), ∥ · ∥_{X}^{2}) ⩽ C′(X) for every j ∈ ℕ.

Proof. Fix k ∈ ℕ which will be determined presently. Write t_{0} = (2k)^{3k}, and let i_{0} be the smallest i ∈ ℕ such that n_{i} ⩾ e^{(4t_{0})^{k}}. Note that this implies that n_{i_{0}} ⩽ 100e^{(4t_{0})^{k}}. We shall now define inductively a sequence of graphs {F_{j}(k)}_{j=0}^{∞} as follows: F_{0}(k) = H_{i_{0}}(1/k) (from Lemma 2.1). The degree of F_{0}(k) is d_{i_{0}} ⩽ e^{(log n_{i_{0}})^{1−1/k}} and it has n_{i_{0}} vertices. Define F_{1}(k) = 𝒞_{d_{i_{0}}^{2}}(F_{0}(k)), so that the degree of F_{1}(k) is d_{i_{0}}^{2}. Assume inductively that we defined

F_{j}(k) to be a graph with n_{i_{0}}^{j} vertices and degree d_{i_{0}}^{2}. Then 𝒜_{t_{0}}(F_{j}(k)) has n_{i_{0}}^{j} vertices and degree t_{0}d_{i_{0}}^{2(t_{0}−1)} ⩽ n_{i_{0}} (where we used our choice of i_{0}). It follows the we can form the edge completion 𝒞_{n_{i_{0}}}(𝒜_{t_{0}}(F_{j}(k))), which has degree n_{i_{0}}, and therefore it is possible to form the zigzag product

F_{j+1}(k) = (𝒞_{n_{0}}(𝒜_{t_{0}}(F_{j}(k)))) ◯ z F_{0}(k),

which has degree d_{i_{0}}^{2} and n_{i_{0}}^{j+1} vertices.

Let (X, ∥ · ∥_{X}) be a super-reflexive normed space and let δ_{0}(X), γ(X) and ε(X), C(X) be as in Lemma 2.1 and (15), respectively. Assume that k ⩾ 1/δ_{0}(X). Then by Lemma 2.1 we have γ_{+}(F_{0}(k), ∥ · ∥_{X}^{2}) ⩽ γ(X), and therefore also by the basic property of edge completion, γ_{+}(F_{1}(k), ∥ · ∥_{X}^{2}) ⩽ 2γ(X). We can now apply Theorem 1 to get the following recursive estimate:

γ_{+} (F_{j+1}(k), ∥ · ∥_{X}^{2}) ⩽ γ_{+} (𝒞_{n_{0}}(𝒜_{t_{0}}(F_{j}(k))), ∥ · ∥_{X}^{2}) γ_{+} (F_{0}(k), ∥ · ∥_{X}^{2})^{2}

⩽ 2γ_{+} (𝒜_{t_{0}}(F_{j}(k)), ∥ · ∥_{X}^{2}) γ(X)^{2}

⩽^{(15)} 2C(X)γ(X)^{2} max \{1, \frac{γ_{+} (F_{j}(k), ∥ · ∥_{X}^{2})}{t_{0}^{ε(X)}}\}

= 2C(X)γ(X)^{2} max \{1, \frac{γ_{+} (F_{j}(k), ∥ · ∥_{X}^{2})}{(2k)^{3kε(X)}}\} .

It follows by induction that if k ⩾ max {C(X), γ(X), 1/ε(X), 1/δ_{0}(X)} then for all j ∈ ℕ we have γ_{+} (F_{j}(k), ∥ · ∥_{X}^{2}) ⩽ 2C(X)γ(X)^{2}. □

Lemma 2.2 is not the final word. Our goal is to construct a super-expander, i.e., one sequence {H_{i}}_{i=1}^{∞} of bounded degree graphs which is expander family with respect to all super-reflexive Banach spaces. In order to do so, we begin by examining more closely the proof of Theorem 2.2 and the parameters in Lemma 2.1 and in (15).

The proof of Theorem 2.2 gives (i) for each k ∈ ℕ a sequence of graphs {F_{j}(k)}_{j=0}^{∞}, such that F_{j}(k) has degree d_{k} and n_{j}(k) vertices, where {n_{j}(k)}_{j=0}^{∞} is a strictly increasing sequence of integers; (ii) a nondecreasing sequence {C′_{k}}_{k=1}^{∞} such that for every super-reflexive Banach space X, there exists k_{1}(X) ∈ ℕ such that for every integer k ⩾ k_{1}(X) and j ∈ ℕ,

γ_{+} (F_{j}(k), ∥ · ∥_{X}^{2}) ⩽ C′_{k_{1}(X)}.  (16)

¿From the proof of (15) in Section 2.3 we infer that there exist a nondecreasing sequence {C′′_{k}}_{k=1}^{∞} ⊆ (0, ∞) and a nonincreasing sequence {ε_{k}}_{k=1}^{∞} ⊆ (0, 1), such that for any superreflexive Banach space X there exists k_{2}(X) ∈ ℕ such that for any regular graph G and t ∈ ℕ,

γ_{+} (𝒜 _{t}(G), ∥ · ∥_{X}^{2}) ⩽ C′′_{k_{2}(X)} · max \{1, \frac{γ_{+} (G, ∥ · ∥_{X}^{2})}{t^{ε_{k_{2}(X)}}}\} .  (17)

The analogues of properties (16) and (17) for a general family of kernels suffice to prove the following lemma:

Lemma 2.3. Let {F_{j}(k)}_{j,k∈ℕ} be graphs as described before (16), i.e., F_{j}(k) has degree d_{k} and n_{j}(k) vertices, where {n_{j}(k)}_{j=0}^{∞} is strictly increasing. Assume that 𝒦 is a family of kernels such that γ_{+}(F_{j}(k), K) < ∞ for all K ∈ 𝒦 and j, k ∈ ℕ. Assume also that 𝒦 satisfies (16) and (17), i.e.,

• There is a nondecreasing sequence {C′_{k}}_{k=1}^{∞} such that for every K ∈ 𝒦 there exists k_{1}(K) ∈ ℕ such that for every integer k ⩾ k_{1}(K) and j ∈ ℕ,

γ_{+} (F_{j}(k), K) ⩽ C′_{k_{1}(K)}.  (18)

• There exist a nondecreasing sequence {C′′_{k}}_{k=1}^{∞} ⊆ (0, ∞) and a nonincreasing sequence {ε_{k}}_{k=1}^{∞} ⊆ (0, 1), such that for any K ∈ 𝒦 there exists k_{2}(K) ∈ ℕ such that for any regular graph G and t ∈ ℕ,

γ_{+} (𝒜 _{t}(G), K) ⩽ C′′_{k_{2}(K)} · max \{1, \frac{γ_{+} (G, K)}{t^{ε_{k_{2}(K)}}}\} .  (19)

Then there exists d ∈ ℕ and a sequence of d-regular graphs {H_{i}}_{i=1}^{∞} whose number of vertices tends to ∞ with i, such that for every K ∈ 𝒦 there exists C(K) ∈ (0, ∞) satisfying γ_{+}(H_{i}, K) ⩽ C(K) for all i ∈ ℕ.

Proof. Set C_{k} = max {C′_{k}, C′′_{k}} and m_{k} = ⌈(2C_{k}^{3})^{1/ε_{k}}⌉. Let j(k) be the smallest j ∈ ℕ

such that n_{j}(k) > max {k, m_{k+1}d_{k+1}^{2m_{k+1}}}. We define L_{k} = F_{j(k)}(k). While the sequence {γ_{+}(L_{k}, K)}_{k=1}^{∞} is bounded for any K ∈ 𝒦 , this is not yet the desired graph sequence since its degrees are unbounded.

We next define for every k ∈ ℕ a sequence of graphs L_{k,0}, L_{k,1}, …, L_{k,ℓ(k)} as follows. Along with {L_{k,j}}_{j=0}^{ℓ(k)} we shall also define an auxiliary sequence {h_{j}(k)}_{j=0}^{ℓ(k)−1} ⊆ ℕ. Set L_{k,0} = L_{k} and h_{0}(k) = k. Define h_{1}(k) to be the smallest h ∈ ℕ such that n_{j(h)}(h) > d_{h_{0}(k)}. From the definition of j(·), we have that h_{1}(k) < h_{0}(k). Define

L_{k,1} = 𝒜_{m_{h_{1}(k)}} (C_{n_{j(h_{1}(k))}(h_{1}(k))}(L_{k,0}) ◯ z L_{h_{1}(k)}) .

Note that the degree of L_{k,1} is m_{h_{1}(k)}d_{h_{1}(k)}^{2m_{h_{1}(k)}}.

Inductively, assume we have already defined L_{k,i−1}, and h_{i−1}(k), and that the degree of L_{k,i−1} is m_{h_{i−1}(k)}d_{h_{i−1}(k)}^{2m_{h_{i−1}(k)}}. Define h_{i}(k) to be the smallest h ∈ ℕ such that n_{j(h)}(h) >

m_{h_{i−1}(k)}^{2}d_{h_{i−1}(k)}^{2m_{h_{i−1}(k)}}. From the definition of j(·), we have that h_{i}(k) < h_{i−1}(k). Define

L_{k,i} = 𝒜_{m_{h_{i}(k)}} (𝒞_{n_{j(h_{i}(k))}(h_{i}(k))}(L_{k,i−1}) ◯ z L_{h_{i}(k)}) .

Note that the degree of L_{k,i} is m_{h_{i}(k)}d_{h_{i}(k)}^{2m_{h_{i}(k)}}.

Continue this way, until h_{i}(k) = 1. At that point, set ℓ(k) = i + 1, and define

L_{k,ℓ(k)} = 𝒜_{m_{1}}(𝒞_{n_{j(1)}(1)}(L_{k,ℓ(k)−1}) ◯ z L_{1}).

Hence L_{k,ℓ(k)} has degree m_{1}d_{1}^{2m_{1}} which is a universal constant. Define H_{k} = L_{k,ℓ(k)}. We shall now show that {H_{k}}_{k=1}^{∞} is the desired graph sequence.

Fix K ∈ 𝒦 and set k_{0}(K) = max{k_{1}(K), k_{2}(K)}. Now fix k > k_{0}(K). We shall first estimate γ_{+} (L_{k,i}, K), when h_{i}(k) > k_{0}(K). By induction on i we shall show that as long as h_{i}(k) > k_{0}(K), we have γ_{+} (L_{k,i}, K) ⩽ C_{k_{0}(K)}. If h_{0}(k) = k > k_{0}(K) ⩾ k_{1}(K), then by our assumption (18), γ_{+}(L_{k,0}, K) = γ_{+}(F_{j(k)}(k), K) ⩽ C_{k_{0}(K)}. Assume next that h_{i}(k) > k_{0}(K), and inductively that γ_{+}(L_{k,i−1}, K) ⩽ C_{k_{0}(K)}. Then using Theorem 1 and (19),

γ_{+}(L_{k,i}, K) ⩽ C_{k_{0}(K)} · max \{1, \frac{2γ_{+}(L_{k,i−1}, K) · γ_{+}(L_{h_{i}(k)}, K)^{2}}{m_{h_{i}(k)}^{ε_{h_{i}(k)}}} \}

⩽^{(18)} C_{k_{0}(K)} max \{1, \frac{2C_{k_{0}(K)}^{3}}{m_{h_{i}(k)}^{ε_{h_{i}(k)}}} \} ⩽ C_{k_{0}(K)}.

If we let i_{0}(k) be the largest i such that h_{i}(k) > k_{0}(K), then we have just proved that γ_{+}(L_{k,i_{0}(k)}, K) ⩽ C_{k_{0}(K)}. For i > i_{0}(k), we use shall only rough bounds:

γ_{+}(L_{k,i}, K) ⩽ C_{k_{0}(K)} · max \{1, \frac{2γ_{+}(L_{k,i−1}, K) · γ_{+}(L_{h_{i}(k)}, K)^{2}}{m_{h_{i}(k)}^{ε_{h_{i}(k)}}} \}

⩽ 2C_{k_{0}(K)}γ_{+}(L_{h_{i}(k)}, K)^{2}γ_{+}(L_{k,i−1}, K). (20)

By iterating (20) we obtain the crude bound:

γ_{+}(H_{k}, K) = γ_{+}(L_{k,ℓ(k)}, K) ⩽ (2C_{k_{0}}(K))^{k_{0}(K)} ∏_{i=1}^{k_{0}(K)} γ_{+}(L_{i}, K)^{2}.  (21)

The right hand side of (21) depends on K, but not on k. Hence {γ_{+}(H_{k}, K)}_{k=1}^{∞} is bounded for every K ∈ 𝒦 . It remains to argue that the number of vertices of H_{k} tends to ∞ with k. Indeed, the number of vertices in H_{k} is at least as the number of vertices of L_{k} = F_{j(k)}(k) which is n_{j(k)}(k), and from the definition of j(k), we have n_{j(k)}(k) > k. □

Theorem 2 (Existence of super-expanders). There exists a sequence of 9-regular graphs {G_{i}}_{i=1}^{∞}, whose number of vertices tends to ∞ with i, such that for any super-reflexive Banach space (X, ∥ · ∥_{X}) there is C(X) ∈ (0, ∞), such that γ_{+}(G_{i}, ∥ · ∥_{X}^{2}) ⩽ C(X) for every i ∈ ℕ.

Proof. ¿From the discussion before Lemma 2.3, and by Lemma 2.3 itself, we conclude that there exists a universal constant d ∈ ℕ, and d-regular super-expander family {H_{k}}_{k=1}^{∞}, with γ_{+}(H_{k}, ∥ · ∥_{X}^{2}) ⩽ C(X).

Let C_{m}^{∘} be the m-vertex cycle with self-loops. It is an easy consequence of the triangle inequality that for every metric space (Y, d_{Y}) we have γ_{+}(C_{m}^{∘}, d_{Y}^{2} ) ⩽ 4m^{2}. Thus, using Theorem 1 once more we see that for all k ∈ ℕ we have

γ_{+} (H_{k} ◯ z C_{d}^{∘}, ∥ · ∥_{X}^{2}) ⩽ 16d^{4}C(X),

which is a constant depending only on X but not on k. Hence {H_{k} ◯ z C_{d}^{∘}}_{k=1}^{∞} is the required sequence of 9-regular super-expanders. □

Remark 2.1. Similarly, the sequence {(H_{k} ◯ z C_{d}^{o})◯ r C_{9}}_{k=1}^{∞} is a 3-regular super-expander, where, C_{9} is the cycle on 9 vertices (without self-loops), and “◯ r ” is the replacement (graph) product (cf. [38]). In the full version of this extended abstract we analyze the replacement product similarly to the zigzag product analysis presented here.

Remark 2.2. Lafforgue [17] asked whether there exists a sequence of bounded degree graphs {G_{k}}_{k=1}^{∞} which does not admit a coarse embedding (with uniform moduli) into any K-convex Banach space. An examination of Lafforgue’s argument shows the his method produces graphs {H_{j}(k)}_{j,k∈ℕ} such that for each k ∈ ℕ the graphs {H_{j}(k)}_{j∈ℕ} have degree d_{k}, their cardinalities are unbounded, and for every K-convex Banach space (X, ∥ · ∥_{X}^{2}) there is some k ∈ ℕ for which sup_{j∈ℕ} γ_{+}(H_{j}(k), ∥ · ∥_{X}^{2}) < ∞. The problem is that the degrees {d_{k}}_{k∈ℕ} are unbounded, but this can be overcome as above by applying the zigzag product with a cycle with self-loops. Indeed, define G_{j}(k) = H_{j}(k) ◯ z C_{d_{k}}^{∘}. Then G_{j}(k) is 9-regular, and as argued in the proof of Theorem 2, we still have sup_{j∈ℕ} γ_{+}(G_{j}(k), ∥·∥_{X}^{2}) < ∞. To get a single sequence of graphs which does not admit a coarse embedding into any K-convex Banach space, fix a bijection ψ = (a, b) : ℕ → ℕ × ℕ, and define G_{m} = G_{a(m)}(b(m)). The graphs G_{m} all have degree 9. If X is K-convex then choose k ∈ ℕ as above. If we let m_{j} ∈ ℕ be such that ψ(m_{j}) = (j, k) then we have shown that the graphs {G_{m_{j}}}_{j=1}^{∞} are arbitrarily large, have bounded degree, and satisfy sup_{j∈ℕ} γ_{+}(G_{m_{j}}, ∥ · ∥_{X}^{2}) < ∞. The argument that was presented in Section 1.1 implies that {G_{m}}_{m=1}^{∞} do not embed coarsely into X. 2.3. Cesàro averages of matrices: coping with new issues that arise from nonlinearity. The goal in this section is to prove (15), i.e., the spectral calculus inequality for Cesáro averages in super-reflexive spaces.

Recall that we use the following notation 𝒜_{m}(A) = \frac{1}{m} ∑_{t=0}^{m−1} A^{t}. Fix ε > 0 and C ∈ (0, ∞). Assume that a metric space (X, d_{X}) satisfies the following property, which we call metric Markov cotype \frac{2}{ε} with constant C and exponent 2: for every m, n ∈ ℕ, every symmetric stochastic n×n matrix A = (a_{ij}), and every x_{1}, …, x_{n} ∈ X there exist y_{1}, …, y_{n} ∈ X which satisfy the following inequality:

∑_{i=1}^{n} d_{X}(x_{i}, y_{i})^{2} + m^{ε} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(y_{i}, y_{j})^{2} ⩽ C^{2} ∑_{i=1}^{n} ∑_{j=1}^{n} 𝒜_{m}(A)_{ij} d_{X}(x_{i}, x_{j})^{2}.  (22)

The origin of this (admittedly cumbersome) name comes from a key linear property of normed spaces that was introduced by Ball [1] under the name of Markov cotype in his profound work on the Lipschitz extension problem. We will see below that any super-reflexive normed space has metric Markov cotype \frac{2}{ε} with constant C and exponent 2 for some ε ∈ (0, 1] and C ∈ (0, ∞) (our proof uses Ball’s insights in [1]).

Informally, (22) means that the average square distance of the edges in an embedding of the graph \frac{1}{m} ∑_{0}^{m−1} A^{t} into X is larger than the average square distance of the edges in the graph A by a factor of m^{ε}, in a different embedding of the graph A into X, which is near the original embedding. This is formalized in the following claim whose proof is in Section 3.1. Claim 2.4. Assuming that (X, d_{X}) has metric Markov cotype \frac{2}{ε} with constant C and exponent 2, we have:

γ (𝒜_{m}(A), d_{X}^{2}) ⩽ 12C^{2} max \{1, \frac{γ (A, d_{X}^{2})}{m^{ε}}\} .  (23)

In order to deduce (15), which is the variant of (23) for absolute spectral gaps, we need the following two easy consequences of the triangle inequality. The proofs appear in Section 3.1. Claim 2.5. For every doubly stochastic n × n matrix A, and any metric space X,

\frac{2}{5}γ (( \begin{matrix}0 & A \\ A & 0 \end{matrix} ) , d_{X}^{2}) ⩽ γ_{+} (A, d_{X}^{2}) ⩽ 2γ (( \begin{matrix}0 & A \\ A & 0 \end{matrix} ) , d_{X}^{2}) .  (24)

Claim 2.6. For every doubly stochastic n × n matrix A, and any metric space X,

γ (( \begin{matrix}0 & 𝒜_{m}(A) \\ 𝒜_{m}(A) & 0 \end{matrix} ) , d_{X}^{2}) ⩽ 9γ (𝒜_{m} ( \begin{matrix}0 & A \\ A & 0 \end{matrix} ) , d_{X}^{2}) .  (25)

By combining (23) with (24) and (25) we deduce (15) with C(X) ⩽ 540C^{2} whenever (X, d_{X}) satisfies (22).

It remains to explain why any super-reflexive normed space (X, ∥ · ∥_{X}) has metric Markov cotype \frac{2}{ε} with constant C and exponent 2 for some ε, C ∈ (0, ∞). An important theorem of Pisier [31] says that X has an equivalent norm whose modulus of uniform convexity has power type p for some p ∈ [2, ∞). From this fact, together with results from [6, 2], we deduce the following variant of Pisier’s martingale inequality [31], which is proved in Section 3.2:

∑_{k=1}^{m} 𝔼 [∥M_{k} − M_{k−1}∥_{X}^{2}] ≲ m^{1− \frac{2}{p}} 𝔼 [∥M_{m} − M_{0}∥_{X}^{2}] ,  (26)

for every square integrable martingale {M_{k}}_{k=0}^{m} ⊆ X, where the implied constant in (26) depends on X.

In order to deduce (22) from (26) fix x_{1}, …, x_{n} ∈ X and define f : {1, …, n} → X by f(i) = x_{i}. For every ℓ ∈ {1, …, n} let {Z_{t}^{(ℓ)}}_{t=0}^{m} be the Markov chain on {1, …, n} which starts at ℓ and has transition matrix A. In other words Z_{0}^{(ℓ)} = ℓ with probability 1 and for t ∈ {1, …, m}, i, j ∈ {1, …, n} we have Pr[Z_{t}^{(ℓ)} = j|Z_{t−1}^{(ℓ)} = i] = a_{ij}. For t ∈ {0, …, m} define f_{t} : {1, …, n} → X by f_{t}(i) = ∑_{j=1}^{n}(A^{m−t})_{ij}f(j). A simple computation shows that if we set M_{t}^{(ℓ)} = f_{t}(Z_{t}^{(ℓ)}) then {M_{t}^{(ℓ)}}_{t=0}^{m} is a martingale with respect to the filtration induced by {Z_{t}^{(ℓ)}}_{t=0}^{m}. We can therefore apply (26) to this martingale, and then average over ℓ ∈ {1, …, n}, to get the inequality:

∑_{t=1}^{m} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ∥f_{t}(i) − f_{t−1}(j)∥_{X}^{2} ≲ m^{1− \frac{2}{p}} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij} ∥x_{i} − ∑_{r=1}^{n}(A^{m})_{jr}x_{r}∥_{X}^{2} .  (27)

If we choose y_{i} = \frac{1}{m} ∑_{s=0}^{m−1}(A^{s})_{ij}x_{j} for i ∈ \{1 …, n\}, then we can use convexity to deduce the bound:

∑_{t=1}^{m} ∑_{i=1}^{n} ∑_{j=1}^{n}a_{ij} ∥f_{t}(i) − f_{t−1}(j)∥_{X}^{2} ⩾ m ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ∥\frac{1}{m} ∑_{t=1}^{m} (f_{t}(i) − f_{t−1}(j))∥_{X}^{2}

= m ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ∥y_{i} − y_{j} − \frac{1}{m} ∑_{r=1}^{n}(A^{m})_{jr}(x_{j} − x_{r})∥_{X}^{2}

⩾ \frac{m}{2} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ∥y_{i} − y_{j}∥_{X}^{2} − \frac{1}{m} ∑_{j=1}^{n} ∑_{r=1}^{n}(A^{m})_{jr} ∥x_{j} − x_{r}∥_{X}^{2} .  (28)

At the same time we can bound the right-hand side of (27) as follows:

∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij} ∥x_{i} − ∑_{r=1}^{n}(A^{m})_{jr}x_{r}∥_{X}^{2} ⩽ ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{r=1}^{n}(A^{m})_{ij}(A^{m})_{jr} ∥x_{i} − x_{r}∥_{X}^{2}

⩽ 2 ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{r=1}^{n}(A^{m})_{ij}(A^{m})_{jr} (∥x_{i} − x_{j}∥_{X}^{2} + ∥x_{j} − x_{r}∥_{X}^{2})

= 4 ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}∥x_{i} − x_{j}∥_{X}^{2}.  (29)

We note that:

∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}∥x_{i} − x_{j}∥_{X}^{2} = ∑_{i=1}^{n} ∑_{j=1}^{n} (\frac{1}{m} ∑_{t=0}^{m−1} A^{t}A^{m−t})_{ij} ∥x_{i} − x_{j}∥_{X}^{2}

⩽ \frac{2}{m} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{r=1}^{n} ∑_{t=0}^{m−1}(A^{t})_{ir}(A^{m−t})_{rj} (∥x_{i} − x_{r}∥_{X}^{2} + ∥x_{r} − x_{j}∥_{X}^{2})

= 2 ∑_{i=1}^{n} ∑_{j=1}^{n} (\frac{1}{m} ∑_{t=0}^{m−1} A^{t})_{ij} ∥x_{i} − x_{j}∥_{X}^{2} + 2 ∑_{i=1}^{n} ∑_{j=1}^{n} (\frac{1}{m} ∑_{t=1}^{m} A^{t})_{ij} ∥x_{i} − x_{j}∥_{X}^{2}

⩽ 4 ∑_{i=1}^{n} ∑_{j=1}^{n} (\frac{1}{m} ∑_{t=0}^{m−1} A^{t})_{ij} ∥x_{i} − x_{j}∥_{X}^{2} + \frac{2}{m} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}∥x_{i} − x_{j}∥_{X}^{2},

which implies (by separating the cases m ⩾ 4 and m < 4) the bound:

∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}∥x_{i} − x_{j}∥_{X}^{2} ≲ ∑_{i=1}^{n} ∑_{j=1}^{n} (\frac{1}{m} ∑_{t=0}^{m−1} A^{t})_{ij} ∥x_{i} − x_{j}∥_{X}^{2}.  (30)

Substituting (28) and (29) into (27) yields the bound:

m^{2/p} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} ∥y_{i} − y_{j}∥_{X}^{2} ≲ ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}∥x_{i} − x_{j}∥_{X}^{2}

≲^{(30)} ∑_{i=1}^{n} ∑_{j=1}^{n} (\frac{1}{m} ∑_{t=0}^{m−1} A^{t})_{ij} ∥x_{i} − x_{j}∥_{X}^{2}. (31)

At the same time,

∑_{i=1}^{n} ∥x_{i} − y_{i}∥_{X}^{q} = ∑_{i=1}^{n} ∑_{j=1}^{n} ∥\frac{1}{m} ∑_{t=0}^{m−1}(A^{t})_{ij}(x_{i} − x_{j})∥_{X}^{q}

⩽ ∑_{i=1}^{n} ∑_{j=1}^{n} (\frac{1}{m} ∑_{t=0}^{m−1} A^{t})_{ij} ∥x_{i} − x_{j}∥_{X}^{q}. (32)

Inequalities (31) and (32) imply (22) with ε = \frac{2}{p}, as required.

15

2.4. Constructing the base graph: the heat semigroup on the tail space. In this section we outline the proof of Lemma 2.1 — the existence of “sufficiently good” base graphs for the class of K-convex spaces (which contain the class of super-reflexive spaces as a subclass). Some of the details are deferred to Section 3.4.

We begin with few definitions. Let 𝔽_{2} = {0, 1} be the field of two elements, and (X, ∥·∥_{X}) a given normed space. L_{p}(X) denotes the normed space of functions f : V → X, where V is an (implicit) finite set (in this paper, V is the vertex set of some graph, and in this section it is V = 𝔽_{2}^{n}) and the norm is ∥f∥_{L_{p}(X)} = (\frac{1}{|V |} ∑_{x∈V} ∥f(x)∥_{X}^{p})^{1/p}. Given a V × V symmetric stochastic matrix A, we view A as a linear operator over L_{p}(X): For f ∈ L_{p}(X) we define Af as (Af)(i) = ∑_{j} A_{ij}f(j) — essentially we identify A with A ⊗ I_{X}. For f ∈ L_{2}(X), let f̂(A) = 𝔼 [f(x)W_{A}(x)] be the Fourier coefficient corresponding to the Walsh function W_{A}(x) = (−1)^{∑_{i∈A} x_{i}}, where the expectation is with respect to the uniform probability measure on 𝔽_{2}^{n}. Let ∂_{i}f(x) = \frac{f(x+e_{i})−f(x)}{2} (where \{e_{i}\}_{i=1}^{n} is the standard basis) and Δf = ∑_{i=1}^{n} ∂_{i}f.

The starting point of our construction is the example of Khot and Naor [16] of quotients of the hypercube by good codes, as examples of metric spaces for which Bourgain’s embedding theorem [4] is asymptotically sharp. It would be instructive to first recall the argument from [16]. Thinking of the cube 𝔽_{2}^{n} as an n-dimensional vector space over 𝔽_{2}, let C ⊆ 𝔽_{2}^{n} be a linear subspace of dimension at least \frac{n}{10} such that the minimum number of 1’s in any non-zero element of C is m ⩾ \frac{n}{10} (a good code). Given a function f : 𝔽_{2}^{n}/C^{⊥} → X we will think of f as a function defined on all of 𝔽_{2}^{n} which is constant on cosets of C^{⊥}. The following claim is a simple observation of [16]:

Claim 2.7. Let C ⊆ 𝔽_{2}^{n} be a linear code with minimum distance of m, and fix f : 𝔽_{2}^{n} → X which is constant on cosets of C^{⊥}. Then f̂(A) = 0 for all nonempty A ⊆ {1, …, n} of cardinality less than m.

Since ΔW_{A} = |A|W_{A} and the (nonempty) Fourier spectrum of f is supported on sets of size at least m, it follows from Parseval’s identity that if X is a Hilbert space then ∥Δf∥_{L_{2}(X)} ⩾ m∥f − 𝔼 f∥_{L_{2}(X)}. But ∥Δf∥_{L_{2}(X)} = ∥∑_{i=1}^{n} ∂_{i}f∥_{L_{2}(X)} ⩽ ∑_{i=1}^{n} ∥∂_{i}f∥_{L_{2}(X)} and ∥f −𝔼 f∥_{L_{2}(X)}^{2} = \frac{1}{2} 𝔼_{x,y} [∥f(x) − f(y)∥_{2}^{2}]. An application of Cauchy-Schwarz and the fact that m ≍ n now implies that 𝔼_{x,y} [∥f(x) − f(y)∥_{2}^{2}] ≲ \frac{1}{n} ∑_{i=1}^{n} ∥∂_{i}f∥_{L_{2}(X)}^{2}. A moment of thought reveals that this is the desired Poincaré inequality (in the case of Hilbert space), where the graph in question is on the vertex set 𝔽_{2}^{n}/C^{⊥}, and each coset x + C^{⊥} is joined by an edge to the cosets {x + e_{i} + C^{⊥}}_{i=1}^{n}. In fact, this graph has degree logarithmic in the number of vertices, which is much better than the assertion in Lemma 2.1.

In order to make this idea work for a non-Hilbertian normed space X it would be desirable to prove that if f : 𝔽_{2}^{n} → X is in the m-tail space, i.e., the subspace of L_{2}(X), denoted L_{2}^{⩾m}(X), consisting of functions f : 𝔽_{2}^{n} → X with f̂(A) = 0 whenever |A| < m, then ∥Δf∥_{L_{2}(X)} ≳ m∥f∥_{L_{2}(X)}. This fact is false without some additional assumption on the geometry of X — in the full version of this extended abstract we observe that it fails when X = L_{1}. Recall from Section 1.1 that a Banach space X is called K-convex if there exists ε_{0} > 0 and n_{0} ∈ ℕ such that any embedding of ℓ_{1}^{n_{0}} into X incurs distortion at least 1 + ε_{0}. Here we will show that if X is K-convex then there exists δ = δ(X) > 0 such that if f ∈ L_{2}^{⩾m}(X) then

∥Δf∥_{L_{2}(X)} ≳ m^{δ}∥f∥_{L_{2}(X)}.  (33)

While this bound is insufficient for our purpose, from the the proof of (33) we can extract a graph which is more complicated than 𝔽_{2}^{n}/C^{⊥} (but is of independent interest), and whose degree bound to what is claimed in Lemma 2.1, which will serve as the base graph(s) for K-convex spaces.

The key idea is to consider the heat semigroup {T_{t}}_{t>0} of operators given by

(T_{t}f)(x) = ∑_{A⊆[n]} e^{−t|A|}f̂(A)W_{A}(x).

and make use of the following lemma, which is the heart of our argument.

Lemma 2.8. If X is a K-convex Banach Space, and p > 1, then there exist α ⩾ 1, a > 0, such that for every n, m ∈ ℕ, m ⩽ n, every t ⩾ 0, and every f : 𝔽_{2}^{n} → X, f ∈ L_{p}^{⩾m}(X),

∥T_{t}f∥_{L_{p}(X)} ≲ e^{−am min{t,t^{α}}}∥f∥_{L_{p}(X)},  (34)

The proof of Lemma 2.8 is based on deep results of Pisier on holomorphic extensions of the heat semigroup on K-convex spaces [33], and a quantitative version of the proof of a recent factorization theorem of Pisier [34]. The proof is contained in Section 3.4.1.

Note that when m ⩾ 1, Δ is invertible on L_{p}^{⩾m}(X), and moreover we have the identity Δ^{−1} = ∫_{0}^{∞} T_{t}dt, since Δ^{−1}W_{A} = |A|^{−1}W_{A}, and

(∫_{0}^{∞} T_{t}dt) W_{A} = ∫_{0}^{∞} T_{t}W_{A}dt = ∫_{0}^{∞} e^{−t|A|}W_{A}d_{t} = |A|^{−1}W_{A}.

Hence by integrating (34) over t, it immediately implies (33).

Inequality (34) will serve as the basis for our base graph. This is made transparent by the observation that the heat semigroup can be viewed as a noise operator with noise rate \frac{1−e^{−t}}{2} . The following standard claim (whose proof is recalled in Section 3.4) formalizes this statement.

Claim 2.9. For every f : 𝔽_{2}^{n} → X, x ∈ 𝔽_{2}^{n}, and t ∈ (0, ∞),

(T_{t}f)(x) = ∑_{y∈𝔽_{2}^{n}} (\frac{1 − e^{−t}}{2} )^{∥x−y∥_{1}} · (\frac{1 + e^{−t}}{2} )^{n−∥x−y∥_{1}} f(y).  (35)

Hence T_{t} induces a natural weighted graph structure on 𝔽_{2}^{n}: the weight of the edge joining

x, y ∈ 𝔽_{2}^{n} is (\frac{1−e^{−t}}{2} )^{∥x−y∥_{1}} (\frac{1+e^{−t}}{2} )^{n−∥x−y∥_{1}}. Our base graph is “morally” the quotient of this

weighted cube by C^{⊥}. When t ≈ n^{−1/α}, the factor in the right hand side of (34) becomes a constant, and this implies a Poincaré inequality because of the following general estimate (proved in Section 3.4).

Proposition 2.10. Fix a Banach space X, a symmetric stochastic N × N matrix A, and p ⩾ 1. Assume that there exists 1 > λ > 0 such that for every f : [N] → X with ∑_{i=1}^{N} f(i) = 0 we have,

∥Af∥_{L_{p}(X)} ⩽ λ∥f∥_{L_{p}(X)}.  (36)

Then,

γ_{+}(A, ∥ · ∥_{X}^{p}) ⩽ 8^{p}(1 − λ)^{−p}.

Still, “T_{t}/C^{⊥}” is not a low degree unweighted graph. To make it an unweighted graph we first truncate the weights of T_{t} below an appropriate threshold, and approximate the remaining (large enough) weights using multiple parallel edges. This process is summarized in the following lemma (whose proof is deferred to the full version due to lack of space).

Lemma 2.11. Let τ = (1 − e^{−t})/2. There exists a Cayley graph on 𝔽_{2}^{n}, G = (𝔽_{2}^{n}, E), having degree at most τ^{−4τn}(1 − τ)^{−(1−4τ)n} such that for every metric space (X, d_{X}), p ⩾ 1 and f, g : 𝔽_{2}^{n} → X,

\frac{1}{3|E|} ∑_{(x,y)∈E} d_{X}(f(x), g(y))^{p}

⩽ \frac{1}{2^{n}} ∑_{x,y∈𝔽_{2}^{n}}(T_{t})_{xy}d_{X}(f(x), g(y))^{p} ⩽ \frac{3}{|E|} ∑_{(x,y)∈E} d_{X}(f(x), g(y))^{p}, (37)

as long as 18τ^{2}n ⩾ 2p log n + log 4.

Only then we pass to the quotient 𝔽_{2}^{n}/C^{⊥} by identifying vertices within each coset and dividing the number of the resulting “quotient edges” between each coset by |C^{⊥}|. This is formally summarized as the proof of Lemma 2.1.

Proof of Lemma 2.1. The argument works for any power p ∈ (1, ∞) and not just p = 2. Fix a K-convex Banach space X, and let α ⩾ 1 and a > 0 as in Lemma 2.8.

Fix n ∈ ℕ. Set t = min{n^{−1/α}/a, 0.1}, τ = (1−e^{−t})/2 and apply the discretization process — Lemma 2.11 — on T_{t}, from which we obtain a Cayley graph G = G_{n} = (𝔽_{2}^{n}, E) whose degree is at most

τ^{−4τn}(1 − τ)^{(1−4τ)n} ⩽ τ^{−8τn} ⩽ max {40^{320·10^{10α}}, n^{2n^{1−1/aα}/α}/a} ≲ e^{n^{1−δ}},

for some δ = δ(X) ∈ (0, 1), depending only on α and a (and hence on X), but not on n.

Let C ⊆ 𝔽_{2}^{n} be a “good” linear code of dimension at least n/10 and minimum weight m ⩾ n/10. We define H = H_{n} = (𝔽_{2}^{n}/C^{⊥}, E/C^{⊥}): the quotient of G by C^{⊥}, whose vertexset is the set of cosets of C^{⊥} and in the edge (multi)set E/C^{⊥} the number of edges between two cosets x + C^{⊥} and y + C^{⊥}, is the number of edges in G with one endpoint in x + C^{⊥} and the other in y + C^{⊥} divided by |C^{⊥}|. Since C^{⊥} is a linear subspace in a vector space, the degree of H is the same as the degree of G.

Next, fix f : 𝔽_{2}^{n}/C^{⊥} → X with ∑_{x∈𝔽_{2}^{n}/C^{⊥}} f(x) = 0. Thinking on f as a function on

𝔽_{2}^{n} which is constant on cosets of C^{⊥}, we have by Claim 2.7 that f̂(A) = 0 for every ∅ ≠ A ⊆ {1, …, n}, |A| < m. Hence by Lemma 2.8,

∥T_{t}f∥_{L_{p}(X)} ≲ e^{−amt^{α}}∥f∥_{L_{p}(X)} ⩽ λ∥f∥_{L_{p}(X)},

where 0 < λ < 1 is a universal constant. Since this is true for any f : 𝔽_{2}^{n}/C^{⊥} → X with ∑_{x∈𝔽_{2}^{n}/C^{⊥}} f(x) = 0, applying Proposition 2.10 we have that for every f, g : 𝔽_{2}^{n}/C^{⊥} → X,

\frac{|C^{⊥}|^{2}}{2^{2n}} ∑_{x,y∈𝔽_{2}^{n}/C^{⊥}} ∥f(x) − g(y)∥_{X}^{2}

≲ \frac{|C^{⊥}|}{2^{n}} ∑_{x,y∈𝔽_{2}^{n}/C^{⊥}} \frac{1}{|C^{⊥}|} ∑_{a,b∈C^{⊥}}(T_{t})_{x+a,y+b}∥f(x + a) − g(y + b)∥_{X}^{2}  (38)

= \frac{1}{2^{n}} ∑_{x,y∈𝔽_{2}^{n}}(T_{t})_{x,y}∥f(x) − g(y)∥_{X}^{2}

⩽ \frac{3}{|E|} ∑_{(x,y)∈E} ∥f(x) − g(y)∥_{X}^{2}  (39)

= \frac{3}{|E/C^{⊥}|} ∑_{(x,y)∈E/C^{⊥}} ∥f(x) − g(y)∥_{X}^{2}.

The estimate (38) follows from Proposition 2.10, and (39) follows from (37), and is valid since 18τ^{2}n ⩾ 4 log n + log 4. □

2.5. Discussion. In the full version of this extended abstract we will also establish the metric Markov cotype property (22) for other classes of metric spaces, including CAT (0) metric spaces, and in particular simply connected manifolds with non-positive sectional curvature (in which case we can take C = O(1) and ε = 1). We will discuss this notion in detail and show that it implies a slight variant of Ball’s Markov cotype. This fact is new for CAT (0) metric spaces, and hence, in conjunction with Ball’s extension theorem [1], our work implies a new Lipschitz extension theorem for CAT (0) targets: any Lipschitz function from a subset U of a metric space (X, d_{X}) which has Markov type 2 and takes values in a CAT (0) metric space (Y, d_{Y}) can be extended to a Lipschitz function defined on all of X whose Lipschitz constant is larger by at most a constant factor (depending on X). The definition of the notion of Markov type is beyond the scope of this extended abstract: it suffices to say that we can take X to be Hilbert space [1], or L_{p} for p ∈ [2, ∞) and even more generally a normed spaces whose modulus of smoothness has power type 2 [26], a tree, the word metric on a hyperbolic group or a simply connected manifold with pinched sectional curvature [26], series parallel graphs [5], or Alexandrov spaces (in particular manifolds) of non-negative curvature [29]. While we believe that this extension theorem is a key consequence of our work, for lack of space we defer the discussion about it to the full version of this paper.

Another major addition to the full version of this extended abstract will be a different proof of the decay of the Poincaré constant of powers of symmetric stochastic matrices in super-reflexive spaces and in CAT (0) spaces. This proof is based on using norm bounds. The norm bound λ(A, X, p) for a doubly stochastic n × n matrix A in a normed space X is the smallest λ > 0 satisfying (36). The quantity λ(A, ℝ, 2) is the second absolute eigenvalue of A, and Proposition 2.10 shows that it always controls γ_{+}(A, ∥ · ∥_{X}^{p}) from above. We show in the full version that when X is p-convex, λ(A, X, p) also controls γ_{+}(A, ∥·∥_{X}^{p}) from below, and this allows us to obtain a short proof of the decay of γ_{+}(A^{t}, ∥ · ∥_{X}^{p}) as a function of t when X is a p-convex space. This alternative approach has the advantage that it proves the decay of the Poincaré constant of the power of the matrix instead of its Cesáro average, and it is also shorter than the Markov cotype approach. However, in many respects it is less “robust” than the Markov cotype approach taken here, it yields worse bounds, and most importantly, it yields a Poincaré inequality which is insufficient for our construction of zigzag super-expanders. All of these issues will be discussed in the full version.

A major question left open is what are the geometric conditions which allows for “sufficient” decay (for the purposes of our zigzag iteration) of the Poincaré constant. We give an example in Section 3.3 for a metric space in which the decay is insufficient. However, there are natural spaces like L_{∞} and L_{1} for which we do not know the answer. Indeed, it may be the case that any normed space has a sufficient decay.

Another question is what are the geometric conditions on metric spaces for the existence of expanders with respect to those spaces. It is tempting to conjecture that for normed spaces, having such an expander is equivalent to having finite cotype (i.e., ∃ε_{0} > 0, n_{0} ∈ ℕ such that ℓ_{∞}^{n_{0}} does not embed with distortion less than 1 + ε_{0}).

As was mentioned in Section 1.1, it is an open question whether every “classical” expander is also super-expander. In the full version we rule out the most obvious approach to prove such a result: coarsely embedding any expander family in any other expander family. We give an example of two expander families F_{1} and F_{2} such that F_{1} does not coarsely embed in F_{2}.

It seems to be a challenging problem whether in (33) we can take δ = 1. Even in the case X = L_{p}, p ≠ 2, this seems to be unknown. A classical result of Meyer [24] implies that for p ⩾ 2 we can take δ = \frac{1}{2}, but even this improved bound is insufficient for our purpose of constructing a “sufficiently good” base graph.

3. Some Details

3.1. Markov cotype and the decay of γ.

Proof of Claim 2.4. Write B = (b_{ij}) = \frac{1}{m} ∑_{t=0}^{m−1} A^{t}. We may assume that γ (B, d_{X}^{2}) > 12C^{2}, since otherwise we are done. This assumption implies that there exist x_{1}, …, x_{n} ∈ X such that:

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{2} > \frac{12C^{2}}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} b_{ij}d_{X}(x_{i}, x_{j})^{2}.  (40)

Let y_{1}, …, y_{n} ∈ X be as in (22). Note that for all i, j ∈ {1, …, n} we have:

d_{X}(x_{i}, x_{j})^{2} ⩽ [d_{X}(x_{i}, y_{i}) + d_{X}(y_{i}, y_{j}) + d_{X}(y_{j}, x_{j})]^{2}

⩽ 3d_{X}(x_{i}, y_{i})^{2} + 3d_{X}(y_{i}, y_{j})^{2} + 3d_{X}(y_{j}, x_{j})^{2}. (41)

By averaging (41) we get the bound:

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(y_{i}, y_{j})^{2} ⩾ \frac{1}{3n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{2} − \frac{2}{n} ∑_{i=1}^{n} d_{X}(x_{i}, y_{i})^{2}

= \frac{1}{6n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{2} + \frac{1}{6n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{2} − \frac{2}{n} ∑_{i=1}^{n} d_{X}(x_{i}, y_{i})^{2}

>^{(40)} \frac{1}{6n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{2} + \frac{2C^{2}}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} b_{ij}d_{X}(x_{i}, x_{j})^{2} − \frac{2}{n} ∑_{i=1}^{n} d_{X}(x_{i}, y_{i})^{2}

⩾^{(22)} \frac{1}{6n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{2}.  (42)

Using (22) once more, in conjunction with the definition of γ (A, d_{X}^{2}), we see that:

C^{2} ∑_{i=1}^{n} ∑_{j=1}^{n} b_{ij}d_{X}(x_{i}, x_{j})^{2} ⩾ \frac{m^{ε}}{γ(A, d_{X}^{2})} · \frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(y_{i}, y_{j})^{2}

>^{(42)} \frac{m^{ε}}{6γ(A, d_{X}^{2})} · \frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{2}.

This concludes the proof of (23). □ Proof of Claim 2.5. Fix f, g : [n] → X, and define h : [2n] → X,

h(x) = \begin{cases}f(x) & x ⩽ n \\ g(x − n) & x > n. \end{cases}

Then

\frac{1}{n^{2}} ∑_{x,y∈[n]} d_{X}(f(x), g(y))^{2} = \frac{1}{n^{2}} ∑_{x,y∈[n]} d_{X}(h(x), h(y + n))^{2}

⩽ \frac{2}{(2n)^{2}} ∑_{x,y∈[2n]} d_{X}(h(x), h(y))^{2}

⩽ γ (( \begin{matrix}0 & A \\ A & 0 \end{matrix} ) , d_{X}^{2}) \frac{2}{2n} ∑_{x,y∈[n]} 2A_{xy}d_{X}(h(x), h(y + n))^{2}

= \frac{2γ (( \begin{matrix}0 & A \\ A & 0 \end{matrix} ) , d_{X}^{2})}{n} ∑_{x,y∈[n]} A_{xy}d_{X}(f(x), g(y))^{2}.

We next prove the lower bound. Fix h : [2n] → X, and define f, g : [n] → X, f(x) = h(x), and g(x) = h(x + n). Then,

\frac{1}{n^{2}} ∑_{x,y∈[n]} d_{X}(h(x), h(y))^{2} ⩽ \frac{1}{n^{2}} ∑_{x,y∈[n]} 2 ∑_{z∈[n]} ( d_{X}(h(x), h(z + n))^{2} + d_{X}(h(y), h(z + n))^{2})

= \frac{4}{n^{2}} ∑_{x,y∈[n]} d_{X}(f(x), g(y))^{2}.

Similarly,

\frac{1}{n^{2}} ∑_{x,y∈[n]} d_{X}(h(x + n), h(y + n))^{2}

⩽ \frac{1}{n^{2}} ∑_{x,y∈[n]} 2 ∑_{z∈[n]} ( d_{X}(h(x + n), h(z))^{2} + d_{X}(h(y + n), h(z))^{2})
= \frac{4}{n^{2}} ∑_{x,y∈[n]} d_{X}(f(x), g(y))^{2}.

Hence, by summing the above two inequalities,

\frac{1}{(2n)^{2}} ∑_{x,y∈[2n]} d_{X}(h(x), h(y))^{2}

= \frac{1}{(2n)^{2}} ∑_{x,y∈[n]} d_{X}(h(x), h(y))^{2} + \frac{1}{(2n)^{2}} ∑_{x,y∈[n]} d_{X}(h(x + n), h(y + n))^{2}

+ \frac{1}{(2n)^{2}} ∑_{x,y∈[n]} d_{X}(h(x), h(y + n))^{2} + \frac{1}{(2n)^{2}} ∑_{x,y∈[n]} d_{X}(h(x + n), h(y))^{2}

⩽ \frac{1 + 1 + 0.25 + 0.25}{n^{2}} ∑_{x,y∈[n]} d_{X}(f(x), g(y))^{2}

⩽ \frac{2.5γ_{+}(G, d_{X}^{2})}{n} ∑_{x,y∈[n]} A_{xy}d_{X}(f(x), g(y))^{2}

= \frac{2.5γ_{+}(G, d_{X}^{2})}{n} ∑_{x,y∈[n]} A_{xy}d_{X}(h(x), h(y + n))^{2}.  □

Proof of Claim 2.6. We observe that for odd t, ( \begin{matrix}0 & A \\ A & 0 \end{matrix} )^{t} = ( \begin{matrix}0 & A^{t} \\ A^{t} & 0 \end{matrix} ). What complicates matters is that for even t, ( \begin{matrix}0 & A \\ A & 0 \end{matrix} )^{t} = ( \begin{matrix}A^{t} & 0 \\ 0 & A^{t} \end{matrix} ). However, we can write every even t > 0 as a sum of two almost unique odd numbers by defining for even t, o_{1}(t) ⩽ o_{2}(t) the unique pair of odd numbers such that o_{2}(t) − o_{1}(t) ⩽ 2, and o_{1}(t) + o_{2}(t) = t. Note that the multiset

{o_{1}(t), o_{2}(t) : t is even, and t ⩽ m}

contains all the odd numbers in the range {1, … ⌊m/2⌋+1}, and at most four items for each value. Let B = ( \begin{matrix}0 & A \\ A & 0 \end{matrix} ). We therefore can bound for every h : [2n] → X,

\frac{1}{2n} ∑_{x,y∈[2n]}(𝒜_{m}(B))_{xy}d_{X}(h(x), h(y))^{2} = \frac{1}{2nm} ∑_{t=0}^{m−1} ∑_{x,y∈[2n]}(B^{t})_{xy}d_{X}(h(x), h(y))^{2}

⩽ \frac{1}{2nm} ∑_{\begin{matrix}t∈[m] \\ t is odd \end{matrix}} ∑_{x,y∈[2n]}(B^{t})_{xy}d_{X}(h(x), h(y))^{2} + \frac{1}{2nm} ∑_{x∈[2n]} d_{X}(h(x), h(x))^{2}

+ \frac{1}{2nm} ∑_{\begin{matrix}t∈\{2,...,m−1\} \\ t is even \end{matrix}} 2( ∑_{x,y∈[2n]}(B^{o_{1}(t)})_{xy}d_{X}(h(x), h(y))^{2} + ∑_{x,y∈[2n]}(B^{o_{2}(t)})_{xy}d_{X}(h(x), h(y))^{2})

⩽ \frac{9}{2nm} ∑_{\begin{matrix}t∈[m] \\ t is odd \end{matrix}} ∑_{x,y∈[2n]}(B^{t})_{xy}d_{X}(h(x), h(y))^{2}

= \frac{9}{2nm} ∑_{\begin{matrix}t∈[m] \\ t is odd \end{matrix}} ∑_{x,y∈[2n]}( \begin{matrix}0 & A^{t} \\ A^{t} & 0 \end{matrix} )_{xy}d_{X}(h(x), h(y))^{2}

⩽ \frac{9}{2n} ∑_{x,y∈[2n]}( \begin{matrix}0 & 𝒜 _{m}(A) \\ 𝒜 _{m}(A) & 0 \end{matrix} )d_{X}(h(x), h(y))^{2}.

Hence

\frac{1}{(2n)^{2}} ∑_{x,y∈[2n]} d_{X}(h(x), h(y))^{2} ⩽ \frac{γ (𝒜 _{m}( \begin{matrix}0 & A \\ A & 0 \end{matrix} ), d_{X}^{2})}{2n} · ∑_{x,y∈[2n]} (𝒜_{m}( \begin{matrix}0 & A \\ A & 0 \end{matrix} )) _{xy} d_{X}(h(x), h(y))^{2}

⩽ \frac{9γ (𝒜 _{m}( \begin{matrix}0 & A \\ A & 0 \end{matrix} ), d_{X}^{2})}{2n} · ∑_{x,y∈[2n]}( \begin{matrix}0 & 𝒜 _{m}(A) \\ 𝒜 _{m}(A) & 0 \end{matrix} )d_{X}(h(x), h(y))^{2},

which means that

γ (( \begin{matrix}0 & 𝒜 _{m}(A) \\ 𝒜 _{m}(A) & 0 \end{matrix} ), d_{X}^{2}) ⩽ 9γ (𝒜 _{m}( \begin{matrix}0 & A \\ A & 0 \end{matrix} ), d_{X}^{2}) .  □

3.2. Proof of (26). Our methods here are inspired by Ball’s proof [1] of the Markov cotype property. Let (X, ∥ · ∥_{X}) be a normed space. The modulus of uniform convexity of X is defined for ε ∈ [0, 2] as

δ_{X}(ε) = inf \{1 − \frac{∥x + y∥_{X}}{2} : x, y ∈ X, ∥x∥_{X} = ∥y∥_{X} = 1, ∥x − y∥_{X} = ε \} .  (43)

A normed space X is said to be uniformly convex if δ_{X}(ε) > 0 for all ε ∈ (0, 2]. Furthermore, X is said to have modulus of convexity of power type p if there exists a constant c such that δ(ε) ⩾ c ε^{p} for all ε ∈ [0, 2]. It is straightforward to check that in this case necessarily p ⩾ 2. By Proposition 7 in [2] (see also [6]), X has modulus of convexity of power type p if and only if there exists a constant K > 0 such that for every x, y ∈ X

2 ∥x∥_{X}^{p} + \frac{2}{K^{p}} ∥y∥_{X}^{p} ⩽ ∥x + y∥_{X}^{p} + ∥x − y∥_{X}^{p}.  (44)

The least K for which (44) holds is called the p-convexity constant of X, and is denoted K_{p}(X).

The following lemma is stated and proved in [1] when p = 2.

Lemma 3.1. Let X be a normed space and U a random vector in X with 𝔼 ∥U∥_{X}^{p} < ∞. Then

∥ 𝔼 U∥_{X}^{p} + \frac{𝔼 ∥U − 𝔼 U∥_{X}^{p}}{(2^{p−1} − 1)K_{p}(X)^{p}} ⩽ 𝔼 ∥U∥_{X}^{p}.  (45)

Proof. We repeat here the p > 2 variant of the argument from [1] for the sake of completeness. Define

θ = inf\{\frac{𝔼 ∥V ∥_{X}^{p} − ∥ 𝔼 V ∥_{X}^{p}}{𝔼 ∥V − 𝔼 V ∥_{X}^{p}} : V ∈ L_{p}(X) ∧ 𝔼 ∥V − 𝔼 V ∥_{X}^{p} > 0\}.  (46)

Then θ ⩾ 0. Our goal is to show that

θ ⩾ \frac{1}{(2^{p−1} − 1)K_{p}(X)^{p}} .  (47)

Fix ϕ > θ. Then there exists a random vector V_{0} ∈ L_{p}(X) for which

ϕ 𝔼 ∥V_{0} − 𝔼 V_{0}∥_{X}^{p} > 𝔼 ∥V_{0}∥_{X}^{p} − ∥ 𝔼 V_{0}∥_{X}^{p}.  (48)

Fix K > K_{p}(X). Apply the inequality (44) point-wise to the vectors x = \frac{1}{2}V_{0} + \frac{1}{2} 𝔼 V_{0} and y = \frac{1}{2}V_{0} − \frac{1}{2} 𝔼 V_{0}, to get that

2 ∥\frac{1}{2}V_{0} + \frac{1}{2} 𝔼 V_{0}∥_{X}^{p} + \frac{2}{K^{p}} ∥\frac{1}{2}V_{0} − \frac{1}{2} 𝔼 V_{0}∥_{X}^{p} ⩽ ∥V_{0}∥_{X}^{p} + ∥ 𝔼 V_{0}∥_{X}^{p}.  (49)

ϕ 𝔼∥V_{0} − 𝔼 V_{0}∥_{X}^{p} >^{(48)} 𝔼 ∥V_{0}∥_{X}^{p} − ∥ 𝔼 V_{0}∥_{X}^{p}

⩾^{(49)} 2 (𝔼 ∥\frac{1}{2}V_{0} + \frac{1}{2} 𝔼 V_{0}∥_{X}^{p} − ∥𝔼 (\frac{1}{2}V_{0} + \frac{1}{2} 𝔼 V_{0})∥_{X}^{p}) + \frac{2}{K^{p}} 𝔼 ∥\frac{1}{2}V_{0} − \frac{1}{2} 𝔼 V_{0}∥_{X}^{p}

⩾^{(46)} 2 𝔼 ∥(\frac{1}{2}V_{0} + \frac{1}{2} 𝔼 V_{0}) − 𝔼 (\frac{1}{2}V_{0} + \frac{1}{2} 𝔼 V_{0})∥_{X}^{p} + \frac{2}{K^{p}} 𝔼 ∥\frac{1}{2}V_{0} − \frac{1}{2} 𝔼 V_{0}∥_{X}^{p}

= (\frac{θ}{2^{p−1}} + \frac{1}{2^{p−1}K^{p}} ) 𝔼 ∥V_{0} − 𝔼 V_{0}∥_{X}^{p}.

Thus

ϕ ⩾ \frac{θ}{2^{p−1}} + \frac{1}{2^{p−1}K^{p}} .  (50)

Since (50) holds for all ϕ > θ and K > K_{p}(X), the desired lower bound (47) follows. □

Let X be a Banach space with K_{p}(X) < ∞. Assume that {M_{k}}_{k=0}^{n} ⊆ X is a martingale with respect to the filtration F_{0} ⊆ F_{1} ⊆ ⋯ ⊆ F_{n−1}; that is, 𝔼 (M_{i+1}|F_{i}) = M_{i} for every i ∈ {0, 1, …, n − 1}. Lemma 3.1 implies that

𝔼[ ∥M_{n} − M_{0}∥_{X}^{p}| F_{n−1}]

⩾ ∥𝔼 [M_{n} − M_{0}| F_{n−1}]∥_{X}^{p} + \frac{𝔼 [∥M_{n} − M_{0} − 𝔼 [M_{n} − M_{0}| F_{n−1}]∥_{X}^{p}| F_{n−1}]}{(2^{p−1} − 1)K_{p}(X)^{p}}

= ∥M_{n−1} − M_{0}∥_{X}^{p} + \frac{𝔼 [∥M_{n} − M_{n−1}∥_{X}^{p}| F_{n−1}]}{(2^{p−1} − 1)K_{p}(X)^{p}}.  (51)

Taking expectation in (51) implies that

𝔼 [∥M_{n} − M_{0}∥_{X}^{p}] ⩾ 𝔼 [∥M_{n−1} − M_{0}∥_{X}^{p}] + \frac{𝔼 [∥M_{n} − M_{n−1}∥_{X}^{p}]}{(2^{p−1} − 1)K_{p}(X)^{p}}.

Iterating this argument we obtain the following famous inequality of Pisier [31].

Theorem 3 (Pisier [31]). Let X be a Banach space with K_{p}(X) < ∞. Assume that {M_{k}}_{k=0}^{n} ⊆ X is a martingale (with respect some filtration). Then

𝔼 [∥M_{n} − M_{0}∥_{X}^{p}] ⩾ \frac{∑_{k=1}^{n} 𝔼 [∥M_{k} − M_{k−1}∥_{X}^{p}]}{(2^{p−1} − 1)K_{p}(X)^{p}}.

We shall also need the following variant of Pisier’s inequality:

Corollary 3.2. For every p, q ∈ (1, ∞) there is a constant c(p, q) ∈ (0, ∞) with the following properties. Let X be a normed space with K_{p}(X) < ∞. Then for every martingale {M_{k}}_{k=0}^{n} ⊆ X, if p ⩽ q, then

𝔼 [∥M_{n} − M_{0}∥_{X}^{q}] ⩾ \frac{c(p, q)}{K_{p}(X)^{p}} ∑_{k=1}^{n} 𝔼 [∥M_{k} − M_{k−1}∥_{X}^{q}] .  (52)

and if p ⩾ q, then

𝔼 [∥M_{n} − M_{0}∥_{X}^{q}] ⩾ \frac{c(p, q)}{n^{1− \frac{q}{p}} K_{p}(X)^{q}} ∑_{k=1}^{n} 𝔼 [∥M_{k} − M_{k−1}∥_{X}^{q}] .  (53)

Proof. Here we only prove the case q ⩽ p, since it is the only one needed in the sequel. By a theorem of Figiel [6] (combined with [2, Proposition 7]) we have K_{p}(L_{q}(X)) ⩽ CK_{p}(X), where C depends only on p, q. We may therefore apply (44) to the vectors

x = M_{n−1} − M_{0} + \frac{M_{n} − M_{n−1}}{2} ∈ L_{q}(X),
y = \frac{M_{n} − M_{n−1}}{2} ∈ L_{q}(X)

to get

2 (𝔼 [∥M_{n−1} − M_{0} + \frac{M_{n} − M_{n−1}}{2} ∥_{X}^{q}])^{p/q} + \frac{2}{2^{p}CK_{p}(X)^{p}} (𝔼 [∥M_{n} − M_{n−1}∥_{X}^{q}])^{p/q}

⩽ (𝔼 [∥M_{n} − M_{0}∥_{X}^{q}])^{p/q} + (𝔼 [∥M_{n−1} − M_{0}∥_{X}^{q}])^{p/q} . (54)

Assume that {M_{k}}_{k=0}^{n} ⊆ X is a martingale with respect to the filtration F_{0} ⊆ F_{1} ⊆ ⋯ ⊆ F_{n−1}. Then

𝔼 [∥M_{n−1} − M_{0}∥_{X}^{q}] = 𝔼 [∥M_{n−1} − M_{0} + 𝔼 [M_{n} − M_{n−1}| F_{n−1}]∥_{X}^{q}] ⩽ 𝔼 [∥M_{n} − M_{0}∥_{X}^{q}] ,

and

𝔼 [∥M_{n−1} − M_{0}∥_{X}^{q}] = 𝔼 [∥M_{n−1} − M_{0} + 𝔼 [ \frac{M_{n} − M_{n−1}}{2} | F_{n−1}]∥_{X}^{q}]

⩽ 𝔼 [∥M_{n−1} − M_{0} + \frac{M_{n} − M_{n−1}}{2} ∥_{X}^{q}] .

Thus (54) implies that

(𝔼 [∥M_{n−1} − M_{0}∥_{X}^{q}])^{p/q} + \frac{(𝔼 [∥M_{n} − M_{n−1}∥_{X}^{q}])^{p/q}}{2^{p}CK_{p}(X)^{p}} ⩽ (𝔼 [∥M_{n} − M_{0}∥_{X}^{q}])^{p/q} . (55)

Applying (55) inductively we get the lower bound

2^{p}CK_{p}(X)^{p} (𝔼 [∥M_{n} − M_{0}∥_{X}^{q}])^{p/q} ⩾ ∑_{k=1}^{n} (𝔼 [∥M_{k} − M_{k−1}∥_{X}^{q}])^{p/q}

⩾ \frac{1}{n^{\frac{p}{q} −1}} (∑_{k=1}^{n} 𝔼 [∥M_{k} − M_{k−1}∥_{X}^{q}])^{p/q} ,

which is precisely (53). □

Note that Corollary 3.2 specialized to q = 2 is precisely (26).

3.3. A metric space without uniform decay of the Poincaré constant. Observe that as long as a metric space (X, d_{X}) contains at least two points, the fact that γ_{+}(A, d_{X}^{p}) < ∞ implies that A is ergodic, and therefore lim_{t→∞} γ_{+}(A^{t}, d_{X}^{p}) = lim_{t→∞} γ_{+}(𝒜_{t}(A), d_{X}^{p}) = 1. However this weak decay is insufficient for our purposes. For the iterative construction in this paper we need at the very least the following type of uniform decay of the Poincaré constant:

∀M > 1 ∃t ∈ ℕ ∃s_{0} ∈ [1, ∞) ∀n ∈ ℕ ∀A ∈ M_{n}(ℝ) symmetric & stochastic,

γ_{+}(A, d_{X}^{p}) ⩾ s_{0} ⟹ γ_{+}(𝒜_{t}(A), d_{X}^{p}) ⩽ \frac{γ_{+}(A, d_{X}^{p})}{M}.

Here we show that there exists a metric space with no such uniform decay.

Proposition 3.3. There exists a metric space (X, ρ), and graphs {G_{n} = (V_{n}, E_{n})}_{n=1}^{∞}, where |V_{n}| = n, such that lim_{n→∞} γ_{+}(G_{n}, ρ^{2}) = ∞, and for every t ∈ ℕ, there exists N_{0} such that for every n > N_{0}, γ_{+}(𝒜_{t}(G_{n}), ρ^{2}) ⩾ \frac{1}{2}γ_{+}(G_{n}, ρ).

Proof. Let G_{n} = (V_{n}, E_{n}) be an arbitrary family of constant degree expanders, i.e., G_{n} is a degree d (say d = 4), n-vertex graph satisfying γ_{+}(G_{n}, ∥ · ∥_{2}^{2}) ⩽ C, for some C > 0. Let (X, ρ) be the metric space defined as follows: as a set, X = ℓ_{∞} ∩ ℤ^{ℵ_{0}}, i.e., the set of all finite integer-valued sequences. The metric ρ on X is given by ρ(x, y) = log(1 + ∥x − y∥_{∞}). Note that ρ is indeed a metric since T (s) = log(1 + s) is concave, increasing and T (0) = 0 (i.e., ρ = T ∘ ∥ · ∥_{∞} is a metric transform of the ℓ_{∞} norm).

First we prove that γ_{+}(G_{n}, ρ^{2}) ≲ (log(1 + log n))^{2}. Let f, g : G_{n} → X be arbitrary mappings. Our goal is to prove that

\frac{1}{n^{2}} ∑_{u,v∈V} ρ(f(u), g(v))^{2} ≲ \frac{(log(1 + log n))^{2}}{nd} ∑_{\{u,v\}∈E} ρ(f(u), f(v))^{2}.

Write S = f(V) ∪ g(V) ⊆ ℤ^{∞}. Let B : (S, ∥ · ∥_{∞}) → ℓ_{2} be the Bourgain embedding [4] of S equipped the ℓ_{∞} norm into ℓ_{2}, i.e., for every u, v ∈ V,

∥f(u) − g(v)∥_{∞} ⩽ ∥B(f(u)) − B(g(v))∥_{2} ⩽ c(1 + log n)∥f(u) − g(v)∥_{∞}.  (56)

for some constant c ⩾ 1.

We next apply the metric transform T (x) = log(1+x) to (56), and obtain for f(u) ≠ g(v),

ρ(f(u), g(v)) = T (∥f(u) − g(v)∥_{∞})
⩽ T (∥B(f(u)) − B(g(v))∥_{2})
⩽ log (1 + c(1 + log n)∥f(u) − g(v)∥_{∞})
⩽ log(c(1 + log n)) + log(2∥f(u) − g(v)∥_{∞})
≲ log(1 + log n) · ρ(f(u), g(v)).  (57)

The second and last inequalities above follow from the fact that ∥f(u) − g(v)∥_{∞} ⩾ 1.

As was shown in [22, Remark 5.4], there exists a universal constant c′ > 1 and a mapping ϕ : ℓ_{2} → ℓ_{2} such that for all x, y ∈ ℓ_{2} we have T (∥x − y∥_{2}) ⩽ ∥ϕ(x)−ϕ(y)∥_{2} ⩽ c′T (∥x − y∥_{2}). This fact, together with (57), implies that the mapping ψ = ϕ ∘ B : S → ℓ_{2} satisfies:

ρ(f(u), g(v)) ⩽ ∥ψ(f(u)) − ψ(g(v))∥_{2} ≲ log(1 + log n) · ρ(f(u), g(v)),

for every u, v ∈ V. Applying the Poincaré inequality of G in ℓ_{2} we conclude that

\frac{1}{n^{2}} ∑_{u,v∈V} ρ(f(u), g(v))^{2} ⩽ \frac{1}{n^{2}} ∑_{u,v∈V} ∥ψ(f(u)) − ψ(g(v))∥_{2}^{2}

≲ \frac{1}{nd} ∑_{(u,v)∈E} |ψ(f(u)) − ψ(g(v))∥_{2}^{2} ≲ \frac{(log(1 + log n))^{2}}{nd} ∑_{(u,v)∈E} ρ(f(u), g(v))^{2}.

This proves that γ_{+}(G_{n}, ρ^{2}) ≲ (log(1 + log n))^{2}.

Next, we show a lower bound on γ_{+}(𝒜_{t}(G), ρ). For this purpose it is sufficient to examine a specific embedding of 𝒜_{t}(G) in X. Let g = f : V → ℤ^{ℵ_{0}} which is an isometric embedding of the shortest path metric on 𝒜_{t}(G) into (ℤ^{ℵ_{0}}, ∥·∥_{∞}). In this case for every {u, v} ∈ E(𝒜_{t}(G)), ρ(f(u), f(v)) = T (∥f(u)−f(v)∥_{∞}) = T (1) = 1. On the other hand, since the degree of 𝒜_{t}(G) is td^{t}, at least half of the pairs in V × V are at distance ≳ \frac{log n}{t log d} in the shortest path metric

metric on 𝒜_{t}(G), and hence their images under f are at ρ-distance ⩾ log (1 + c′′ \frac{log n}{t log d}), where c′′ > 0 is a universal constant. Hence, provided t ⩽ c′′′ log n for some sufficiently small constant c′′′, we have γ_{+}(𝒜_{t}(G), ρ^{2}) ≳ (log (1 + \frac{log n}{t}))^{2}. □

3.4. Construction of the base graph.

Proof of Claim 2.9. The claim easily follows by computing the right hand side in (35) when f = W_{A}. We write x = x_{A}x_{A^{c}}, and

∑_{y∈ 𝔽_{2}^{n}} (\frac{1 − e^{−t}}{2} )^{∥x−y∥_{1}} (\frac{1 + e^{−t}}{2} )^{n−∥x−y∥_{1}} ∏_{i∈A}(−1)^{y_{i}}

= ∑_{y_{A}∈ 𝔽_{2}^{A}} (\frac{1 − e^{−t}}{2} )^{∥x_{A}−y_{A}∥_{1}} (\frac{1 + e^{−t}}{2} )^{|A|−∥x_{A}−y_{A}∥_{1}} ∏_{i∈A}(−1)^{y_{i}}

· ∑_{y_{A^{c}}∈ 𝔽_{2}^{[n]\A}} (\frac{1 − e^{−t}}{2} )^{∥x_{A^{c}}−y_{A^{c}}∥_{1}} (\frac{1 + e^{−t}}{2} )^{n−|A|−∥x_{A^{c}}−y_{A^{c}}∥_{1}}

= ∑_{ℓ=0}^{|A|} \binom{|A|}{ℓ} (\frac{1 − e^{−t}}{2} )^{ℓ} (\frac{1 + e^{−t}}{2} )^{|A|−ℓ} (−1)^{ℓ}W_{A}(x)

= e^{−t|A|}W_{A}(x).  □

Proof of Proposition 2.10. Let f, g : [N] → X, denote by f̄ = 𝔼 f, and ḡ = 𝔼 g, f̃ = f − f̄, g̃ = g − ḡ. Then ∑_{i=1}^{N} f̃(i) = ∑_{i=1}^{N} g̃(i) = 0, and so by the definition of λ, ∥Af̃∥_{L_{p}(X)} ⩽ λ∥f̃∥_{L_{p}(X)}, and ∥Ag̃∥_{L_{p}(X)} ⩽ λ∥g̃∥_{L_{p}(X)}. Hence

∥ ( \begin{matrix}0 & A \\ A & 0 \end{matrix} ) (f̃⊕ g̃)∥_{L_{p}(X)}^{p} = \frac{∥Ag̃∥_{L_{p}(X)}^{p} + ∥Af̃∥_{L_{p}(X)}^{p}}{2}

⩽ λ^{p} \frac{∥f̃∥_{L_{p}(X)}^{p} + ∥g̃∥_{L_{p}(X)}^{p}}{2} = λ^{p}∥f̃⊕ g̃∥_{L_{p}(X)}^{p}.

It follows that,

(1 − λ)∥f̃⊕ g̃∥_{L_{p}(X)} ⩽ ∥f̃⊕ g̃∥_{L_{p}(X)} − ∥ ( \begin{matrix}0 & A \\ A & 0 \end{matrix} ) (f̃⊕ g̃)∥_{L_{p}(X)} ⩽ ∥( \begin{matrix}I & −A \\ −A & I \end{matrix} ) (f̃⊕ g̃)∥_{L_{p}(X)} .

So,

\frac{1}{N^{2}} ∑_{i,j∈[N]}∥f(i) − g(j)∥_{X}^{p} ⩽ 2^{p−1}∥f̄− ḡ∥_{X}^{p} + \frac{2^{p−1}}{N^{2}} ∑_{i,j∈[N]} ∥f̃(i) − g̃(j)∥_{X}^{p}

⩽ 2^{p−1}∥f̄− ḡ∥_{X}^{p} + 4^{p−1}(∥f̃∥_{L_{p}(X)}^{p} + ∥g̃∥_{L_{p}(X)}^{p})

= 2^{p−1}∥f̄− ḡ∥_{X}^{p} + 2^{2p−1}∥f̃⊕ g̃∥_{L_{p}(X)}^{p}

⩽ 2^{p−1}∥f̄− ḡ∥_{X}^{p} + 2^{2p−1}(1 − λ)^{−p} ∥( \begin{matrix}I & −A \\ −A & I \end{matrix} ) (f̃⊕ g̃)∥_{L_{p}(X)}^{p} .

Expanding the last term,

∥ ( \begin{matrix}I & −A \\ −A & I \end{matrix} ) (f̃⊕ g̃)∥_{L_{p}(X)}^{p}

= \frac{1}{2N} ∑_{i∈[N]}∥ ∑_{j∈[N]} A_{ij} (f̃(i) − g̃(j))∥_{X}^{p} + \frac{1}{2N} ∑_{i∈[N]}∥ ∑_{j∈[N]} A_{ij} (g̃(i) − f̃(j))∥_{X}^{p}

⩽ \frac{1}{N} ∑_{i,j∈[N]} A_{ij} ∥f̃(i) − g̃(j)∥_{X}^{p}

⩽ 2^{p−1}∥f̄− ḡ∥_{X}^{p} + \frac{2^{p−1}}{N} ∑_{i,j∈[N]} A_{ij}∥f(i) − g(j)∥_{X}^{p}.

We next observe that for any permutation π : [N] → [N] (and p ⩾ 1), ∥f̄ − ḡ∥_{X}^{p} ⩽ \frac{1}{N} ∑_{i} ∥f(i) − g(π(i))∥_{X}^{p}. Since A is symmetric stochastic, it is in the convex hull of the permutation matrices, so we can write A = ∑_{ℓ} α^{ℓ}Π_{ℓ}, where {Π_{ℓ}}_{ℓ} are permutation matrices, and α_{ℓ} ⩾ 0, ∑_{ℓ} α_{ℓ} = 1. Hence,

∥f̄− ḡ∥_{X}^{p} ⩽ ∑_{ℓ} α_{ℓ} \frac{1}{N} ∑_{i,j} Π_{ij}^{ℓ}∥f(i) − g(j)∥_{X}^{p} = \frac{1}{N} ∑_{i,j} A_{ij}∥f(i) − g(j)∥_{X}^{p}.

We conclude that,

\frac{1}{N^{2}} ∑_{i,j∈[N]} ∥f(i) − g(j)∥_{X}^{p} ⩽ \frac{8^{p}(1 − λ)^{−p}}{N} ∑_{i,j∈[N]} A_{ij}∥f(i) − g(j)∥_{X}^{p}.  □

3.4.1. Proof of Lemma 2.8. The Rademacher projection of f is defined by

R_{1}f = ∑_{j=1}^{n} f̂(A)W_{{j}}.

The K-convexity constant of X, denoted K(X), is the smallest constant K such that for every n and every f : 𝔽_{2}^{n} → X,

∥(R_{1}f)∥_{L_{2}(X)}^{2} ⩽ K^{2}∥f∥_{L_{2}(X)}^{2}.

We also define the kth level Rademacher projection by

R_{k}f = ∑_{\begin{matrix}A⊆[n] \\ |A|=k \end{matrix}} f̂(A)W_{A}.

We assume throughout that X is a complex Banach space. The case of Banach spaces over ℝ follows formally from this case by complexification. Extend the heat semi-group T_{z} : L_{p}(X) → L_{p}(X) to z ∈ ℂ, by setting:

T_{z}f = ∑_{A⊆[n]} e^{−z|A|}f̂(A)W_{A}.

Another way to write it is T_{z} = ∑_{k=0}^{n} e^{−zk}R_{k}. We shall use the following deep theorem of Pisier[33]:

Theorem 4 ([33]). For K-convex X, and p ∈ (1, ∞), there exists ϕ, M > such that if | arg z| < ϕ then ∥T_{z}∥_{L_{p}(X)→L_{p}(x)} ⩽ M.

See [21] for bounds on ϕ, M in terms of K(X). We will require the following standard corollary of Theorem 4:

Corollary 3.4. ∥R_{k}∥_{L_{p}(X)→L_{p}(X)} ⩽ Me^{ak}.

Proof. Define a = \frac{π}{tan ϕ}, so that all the points in the segment \{(a, iy) : y ∈ (−π, π)\} have argument at most ϕ. Calculate,

\frac{1}{2π} ∫_{−π}^{π} e^{ikt}T_{a+it}dt = \frac{1}{2π} ∫_{−π}^{π} e^{ikt} ∑_{r=0}^{n} e^{−(a+it)r}R_{r}dt

= \frac{1}{2π} ∑_{r=0}^{n} e^{−ra}R_{r} ∫_{−π}^{π} e^{i(k−r)t}dt = e^{−ka}R_{k},

and therefore, by convexity,

∥R_{k}∥_{L_{p}(X)→L_{p}(X)} ⩽ \frac{e^{ka}}{2π} ∫_{−π}^{π} |e^{ikt}| · ∥T_{a+it}∥_{L_{p}(X)→L_{p}(X)}dt ⩽ Me^{ka}.  □

Corollary 3.5. Assume that ℜz ⩾ 2a. Then

∥T_{z}∥_{L_{p}^{⩾m}(X)→L_{p}^{⩾m}(X)} = ∥∑_{k⩾m} e^{−zk}R_{k}∥_{L_{p}^{⩾m}(X)→L_{p}^{⩾m}(X)}

⩽ ∑_{k⩾m} e^{−2ak} · Me^{ak} = \frac{M}{1 − e^{−a}} e^{−ma}. □

The ensuing argument is a quantitative version of the proof of the main theorem of Pisier in [34]. Let r = 2\sqrt{a^{2} + π^{2}}, and define V = \{z ∈ ℂ : |z| ⩽ r ∧ | arg z| ⩽ ϕ\} (the set V ⊆ ℂ is depicted in Figure 2). Denote V_{0} = {x ± ix tan ϕ : x ∈ [0, 2a)} and V_{1} = {re^{iθ} : |θ| ⩽ ϕ}, so that we have the disjoint union ∂V = V_{0} ∪ V_{1}.

Fix t ∈ (0, 2a). We shall use the Harmonic measure corresponding to V, i.e., the Borel probability measure μ = μ_{t} on ∂V such that for every bounded analytic function on V,

f(t) = ∫_{∂V} f(z)dμ(z).  (58)

We refer to [7] for more information on this topic and the ensuing discussion. It suffices to say here that for a Borel set U ⊆ ∂V, μ_{t}(U) is the probability that Brownian motion

Figure 2. The sector V.

starting at t leaves V at U. Equivalently, by conformal invariance, μ_{t} is the push-forward of the normalized Lebesgue measure on the unit circle S^{1} under the Riemann mapping from the unit disk to V which takes the origin to t.

Let θ = μ(V_{1}), and denote μ = (1 − θ)μ_{0} + θμ_{1}, where μ_{i} is a probability measure on V_{i}, i ∈ {0, 1}. We will require the following standard bound on θ:

Lemma 3.6. We have θ ≍ (\frac{t}{r})^{\frac{π}{2ϕ}}.

Proof. The proof is a simple exercise in conformal invariance. Let 𝔻 denote the unit disk centered at the origin, and let 𝔻_{+} denote the intersection of 𝔻 with the right half plane \{z ∈ ℂ : ℜz ⩾ 0\}. The mapping z ↦ (\frac{z}{r})^{\frac{π}{2ϕ}} is a conformal equivalence between V and 𝔻_{+}. The mapping z ↦ −i\frac{z+i}{z−i} is a conformal equivalence between 𝔻_{+} and the positive quadrant {x + iy : x, y ⩾ 0}, and the mapping z ↦ z^{2} is a conformal equivalence between the positive quadrant and the upper half-plane. Finally, the mapping z ↦ \frac{z−i}{z+i} is a conformal equivalence between the upper half-plane and 𝔻. By composing these mappings, we obtain the following conformal equivalence between V and 𝔻:

F (z) = \frac{− ((\frac{z}{r})^{\frac{π}{2ϕ}} + i)^{2} − i ((\frac{z}{r})^{\frac{π}{2ϕ}} − i)^{2}}{− ((\frac{z}{r})^{\frac{π}{2ϕ}} + i)^{2} + i ((\frac{z}{r})^{\frac{π}{2ϕ}} − i)^{2}} .

Thus, by composing with the conformal automorphism of 𝔻, z ↦ \frac{z−F (t)}{1−\overline{F (t)}z}, we obtain the

mapping G(z) = \frac{F (z)−F (t)}{1−\overline{F (t)}F (z)}, which is a conformal equivalence between V and 𝔻 with G(t) = 0.

By conformal invariance, θ is the length of the arc G(V_{1}) ⊆ ∂𝔻 = S^{1}, divided by 2π. The assertion of Lemma 3.6 now follows from a direct computation. □

Lemma 3.7. For every ε ∈ (0, 1) there exists a bounded analytic function Ψ : V → ℂ, such that Ψ(t) = 1, for every z ∈ V_{0}, |Ψ(z)| ⩽ ε, and for every z ∈ V_{1}, |Ψ(z)| ⩽ ε^{−θ^{−1}+1}.

Proof. The proof is the same as the proof of Claim 2 in [34]. Consider the strip S = {z ∈ ℂ : ℜ(z) ∈ [0, 1]} and for j ∈ {0, 1} let S_{j} = {z ∈ ℂ : ℜ(z) = j}. The argument in Claim 1 in [34] shows that there exists a a conformal equivalence h : V :→ S such that h(t) = θ, h(V_{0}) = S_{0}, h(V_{1}) = S_{1}. Now define Ψ(z) = ε^{1−θ^{−1}h(z)}. □

We next calculate

T_{t} = Ψ(t)T_{t} = ∫_{∂V} Ψ(z)T_{z}dμ(z) = (1 − θ) ∫_{V_{0}} Ψ(z)T_{z}dμ_{0}(z) + θ ∫_{V_{1}} Ψ(z)T_{z}dμ_{1}(z).

Hence, using Lemma 3.7 with ε = e^{−amθ}, we get the bound:

∥T_{t}∥_{L_{p}^{⩾m}(X)→L_{p}^{⩾m}(X)} ⩽ (1 − θ)εM + θε^{1−θ^{−1}}Ce^{−am} ⩽ (M + C)e^{−amθ}.  (59)

Since by Lemma 3.6 we have θ ≍_{ϕ} t^{\frac{π}{2ϕ}} (where the implied constant depends on ϕ), the bound (59), which holds for t ∈ (0, 2a), combined with Corollary 3.5, concludes the proof of Lemma 2.8. □

References

[1] K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2):137–172, 1992.

[2] K. Ball, E. A. Carlen, and E. H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math., 115(3):463–482, 1994.

[3] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric ramsey-type phenomena. Annals of Mathematics, 162(2):643–709, 2005.

[4] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.

[5] B. Brinkman, A. Karagiozova, and J. R. Lee. Vertex cuts, random walks, and dimension reduction in series-parallel graphs. In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 621–630. ACM, New York, 2007.

[6] T. Figiel. On the moduli of convexity and smoothness. Studia Math., 56:121–155, 1976.

[7] J. B. Garnett and D. E. Marshall. Harmonic measure, volume 2 of New Mathematical Monographs. Cambridge University Press, Cambridge, 2008. Reprint of the 2005 original.

[8] M. Gromov. Filling Riemannian manifolds. J. Differential Geom., 18(1):1–147, 1983.

[9] M. Gromov. Asymptotic invariants of infinite groups. In Geometric group theory, Vol. 2 (Sussex, 1991), volume 182 of London Math. Soc. Lecture Note Ser., pages 1–295. Cambridge Univ. Press, Cambridge, 1993.

[10] M. Gromov. Random walk in random groups. Geom. Funct. Anal., 13(1):73–146, 2003.

[11] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the AMS, 43(4):439–561, 2006.

[12] R. C. James. A nonreflexive Banach space that is uniformly nonoctahedral. Israel J. Math., 18:145–155, 1974.

[13] R. C. James. Nonreflexive spaces of type 2. Israel J. Math., 30(1-2):1–13, 1978.

[14] R. C. James and J. Lindenstrauss. The octahedral problem for Banach spaces. In Proceedings of the Seminar on Random Series, Convex Sets and Geometry of Banach Spaces (Mat. Inst., Aarhus Univ., Aarhus, 1974; dedicated to the memory of E. Asplund), pages 100–120. Various Publ. Ser., No. 24, Aarhus Univ., Aarhus, 1975. Mat. Inst.

[15] G. Kasparov and G. Yu. The coarse geometric Novikov conjecture and uniform convexity. Adv. Math., 206(1):1–56, 2006.

[16] S. Khot and A. Naor. Nonembeddability theorems via Fourier analysis. Mathematische Annalen, 334(4):821–852, 2006.

[17] V. Lafforgue. Un renforcement de la propriété (T). Duke Math. J., 143(3):559–602, 2008.

[18] V. Lafforgue. Propriété (T) renforcée Banachique et transformation de Fourier rapide. Preprint, 2009.

[19] N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.

[20] J. Matoušek. On embedding expanders into ℓ_{p} spaces. Israel J. Math., 102:189–197, 1997.

[21] B. Maurey. Type, cotype and K-convexity. In Handbook of the geometry of Banach spaces, Vol. 2, pages 1299–1332. North-Holland, Amsterdam, 2003.

[22] M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451–494, 2004.

[23] M. Mendel and A. Naor. Metric cotype. Ann. of Math. (2), 168(1):247–298, 2008. Preliminary version in SODA ’06.

[24] P.-A. Meyer. Transformations de Riesz pour les lois gaussiennes. In Seminar on probability, XVIII, volume 1059 of Lecture Notes in Math., pages 179–193. Springer, Berlin, 1984.

[25] V. D. Milman and G. Schechtman. Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov.

[26] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromovhyperbolic metric spaces. Duke Math. J., 134(1):165–197, 2006.

[27] A. Naor and Y. Rabani. Spectral inequalities on curved spaces. Preprint, 2005.

[28] A. Naor and L. Silberman. Poincaré inequalities, embeddings, and wild groups. Preprint, 2004.

[29] S. Ohta. Markov type of Alexandrov spaces of nonnegative curvature. To appear in Mathematika, 2008.

[30] N. Ozawa. A note on non-amenability of ℬ(l_{p}) for p = 1, 2. Internat. J. Math., 15(6):557–565, 2004.

[31] G. Pisier. Martingales with values in uniformly convex spaces. Israel J. Math., 20(3-4):326–350, 1975.

[32] G. Pisier. Some applications of the complex interpolation method to Banach lattices. J. Analyse Math., 35:264–281, 1979.

[33] G. Pisier. Holomorphic semigroups and the geometry of Banach spaces. Ann. of Math. (2), 115(2):375– 392, 1982.

[34] G. Pisier. A remark on hypercontractive semigroups and operator ideals. Preprint, 2007.

[35] G. Pisier. Complex interpolation between Hilbert, Banach and operator spaces. Preprint, 2008.

[36] G. Pisier and Q. H. Xu. Random series in the real interpolation spaces between the spaces v_{p}. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 185–209. Springer, Berlin, 1987.

[37] O. Reingold, L. Trevisan, and S. P. Vadhan. Pseudorandom walks on regular digraphs and the RL vs. L problem. In J. M. Kleinberg, editor, STOC, pages 457–466. ACM, 2006.

[38] O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constantdegree expanders. Ann. of Math., 155(1):157–187, 2002.

[39] J. Roe. Lectures on coarse geometry, volume 31 of University Lecture Series. American Mathematical Society, Providence, RI, 2003.

[40] E. Rozenman and S. Vadhan. Derandomized squaring of graphs. In Approximation, randomization and combinatorial optimization, volume 3624 of Lecture Notes in Comput. Sci., pages 436–447. Springer,

    Berlin, 2005. Available from: http://eccc.hpi-web.de/eccc-reports/2005/TR05-092.

Computer Science Division, The Open University of Israel

  E-mail address: mendelma@gmail.com

Courant Institute, New York University

  E-mail address: naor@cims.nyu.edu