ON THE BANACH SPACE VALUED AZUMA INEQUALITY AND SMALL-SET ISOPERIMETRY OF ALON–ROICHMAN GRAPHS

ASSAF NAOR

Abstract. We discuss the connection between the expansion of small sets in graphs, and the Schatten norms of their adjacency matrices. In conjunction with a variant of the Azuma inequality for uniformly smooth normed spaces, we deduce improved bounds on the small-set isoperimetry of Abelian Alon–Roichman random Cayley graphs.

1. Introduction

In what follows all graphs are allowed to have multiple edges and loops. For a finite group Γ of cardinality n, the Cayley graph associated to the group elements g_{1}, …, g_{k} ∈ Γ is the 2k-regular graph G = (V, E), where V = Γ, and the number of edges joining u, v ∈ Γ equals |{i ∈ {1, …, n} : uv^{−1} = g_{i}}| + |{i ∈ {1, …, n} : uv^{−1} = g_{i}^{−1}}|.

For a graph G = (V, E) and S ⊆ V, let e_{G}(S, V ∖S) denote the size of the edge boundary of S, i.e., the number of edges joining S and its complement. The Alon–Roichman theorem [3] asserts that random Cayley graphs obtained by choosing k group elements independently and uniformly at random are good expanders, provided k is large enough:

Theorem 1.1 (Alon–Roichman theorem). For every ε ∈ (0, 1) there exists c(ε) ∈ (0, ∞) with the following property. Let Γ be a finite group of cardinality n. Assume that k ⩾ c(ε) log n. Then with probability at least \frac{1}{2} over g_{1}, …, g_{k} chosen independently and uniformly at random from Γ, if G is the Cayley graph associated to g_{1}, …, g_{k}, then for every ∅ ≠ S ⊊ Γ we have

| \frac{e_{G}(S, V ∖ S)}{\frac{2k}{n}|S|(n − |S|)} − 1| ⩽ ε.

Subsequent investigations by several authors [17, 11, 14, 22, 8] yielded new proofs, with various improvements, of the Alon–Roichman theorem. The best known upper bound on c(ε) is O(1/ε^{2}); see [8] for the best known estimate on the implied constant.

Here we obtain an improved estimate on the isoperimetric profile of random Cayley graphs of Abelian groups:

Theorem 1.2. There exists a universal constant c ∈ (0, ∞) with the following property. Let Γ be an Abelian group of cardinality n. Assume that k ⩾ \frac{c log n}{ε^{2}}. Then with probability at least \frac{1}{2} over g_{1}, …, g_{k} chosen independently and uniformly at random from Γ, if G is the Cayley graph associated to g_{1}, …, g_{k}, then for every S ⊆ Γ with 2 ⩽ |S| ⩽ \frac{n}{2} we have

| \frac{e_{G}(S, V ∖ S)}{\frac{2k}{n}|S|(n − |S|)} − 1| ⩽ ε\sqrt{\frac{log |S|}{log n}}.  (1)

Research supported in part by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

The possible validity of an estimate such as (1) for finite groups Γ that are not necessarily Abelian remains an interesting open question.

When k = o(log n), the graphs G of Theorem 1.2 need not be connected, and they are never expanders [3, Prop. 3]. Nevertheless, with positive probability, sufficiently small sets in such graphs do have a large edge boundary:

Theorem 1.3. There exists a universal constant c ∈ (0, ∞) with the following property. Let Γ be an Abelian group of cardinality n. Fix k ∈ ℕ and ε ∈ (0, 1). Then with probability at least \frac{1}{2} over g_{1}, …, g_{k} chosen independently and uniformly at random from Γ, if G is the Cayley graph associated to g_{1}, …, g_{k}, then for every ∅ ≠ S ⊊ Γ we have

|S| ⩽ e^{cε^{2}k} ⟹ | \frac{e_{G}(S, V ∖ S)}{\frac{2k}{n}|S|(n − |S|)} − 1| ⩽ ε.

The main purpose of this note is not to obtain results such as Theorem 1.2 and Theorem 1.3, even if these have independent interest. Our goal is rather to present a method to prove expansion of small sets, going beyond the standard spectral gap techniques. In addition, we highlight a simple and general geometric argument that allows one to reason about such questions for random objects like Alon–Roichman graphs. The rest of this introduction will therefore be devoted to a description these issues. We note that a draft of this manuscript has been circulating for several years, and we were motivated to make it publicly available since the ideas presented here inspired recent progress in theoretical computer science; see [5].

1.1. Schatten bounds and small-set expansion. For an n-vertex graph G = (V, E) and u, v ∈ V, let e(u, v) denote the number of edges joining u and v if u ≠ v, and twice the number of loops at u if u = v. If G is d-regular, then the normalized adjacency matrix of G is the n × n matrix A(G) whose entry at (u, v) ∈ V × V equals e(u, v)/d. We will denote by 1 = λ_{1}(G) ⩾ λ_{2}(G) ⩾ ⋯ ⩾ λ_{n}(G) the decreasing rearrangement of the eigenvalues of A(G).

The well-established connection, due to [2, 19] (see also [4, Thm. 9.2.1]), between spectral gaps and graph expansion, reads as follows: for every ∅ ≠ S ⊊ V we have

| \frac{e_{G}(S, V ∖ S)}{\frac{d}{n}|S|(n − |S|)} − 1| ⩽ max_{i∈\{2,...,n\}} |λ_{i}(G)|.  (2)

Let L_{2}(V) denote the vector space ℂ^{V}, equipped with the standard scalar product

∀ x, y : V → ℂ, ⟨x, y⟩ =^{def} \frac{1}{n} ∑_{u∈V} x(u)\overline{y(u)}.

The following lemma is a natural variant of the bound (2).

Lemma 1.4. Fix p ∈ [1, ∞]. Assume that L_{2}(V) has an orthonormal basis consisting of eigenvectors of A(G), all of whose entries are bounded by 1 in absolute value. Then for every ∅ ≠ S ⊊ V we have,

| \frac{e_{G}(S, V ∖ S)}{\frac{d}{n}|S|(n − |S|)} − 1| ⩽ (∑_{i=2}^{n} |λ_{i}(G)|^{p})^{\frac{1}{p}} (\frac{|S|^{\frac{1}{p+1}} (n − |S|)^{\frac{p}{p+1}} + |S|^{\frac{p}{p+1}} (n − |S|)^{\frac{1}{p+1}}}{n} )^{\frac{p+1}{p}} .

See Lemma 3.1 below for a more general version of Lemma 1.4, which does not require the existence of an orthonormal basis with good L_{∞} bounds. We chose to state the above simpler version of Lemma 3.1 in the introduction, since the assumption of Lemma 1.4 holds automatically for Cayley graphs of Abelian groups, where the orthonormal basis in question consists of the characters of the group.

Alon and Roichman [3], as well as the subsequent work [17, 11, 14, 22, 8], proved Theorem 1.1 by showing that, under the assumptions appearing in the statement of Theorem 1.1, we have max_{i∈{2,...,n}} |λ_{i}(G)| ⩽ ε, and then appealing to (2). We will prove Theorem 1.2 and Theorem 1.3 by applying Lemma 1.4 with an appropriate choice of p (depending on the cardinality of S). With this goal in mind, we need to be able to argue about the quantity (∑_{i=2}^{n} |λ_{i}(G)|^{p})^{1/p} when G is the random graph appearing in Theorem 1.2. This can be done via simple geometric considerations from Banach space theory.

1.2. Banach space valued concentration. The singular values of an n×n matrix A, i.e., the eigenvalues of \sqrt{A^{∗}A}, are denoted s_{1}(A) ⩾ s_{2}(A) ⩾ ⋯ ⩾ s_{n}(A). For p ∈ [1, ∞], the Schatten p-norm of A, denoted ∥A∥_{S_{p}}, is defined to be (∑_{i=1}^{n} s_{i}(A)^{p})^{1/p}. Thus, the quantity (∑_{i=2}^{n} |λ_{i}(G)|^{p})^{1/p} appearing in Lemma 1.4 equals ∥(I − \frac{1}{n}J) A(G)∥_{S_{p}} , where I is the n × n identity matrix and J is the n × n matrix all of whose entries are 1.

Fix a group Γ of cardinality n. Let R : Γ → GL(L_{2}(Γ)) be the right regular representation, i.e., (R(g)ϕ)(h) = ϕ(gh) for every ϕ : Γ → ℂ and g, h ∈ Γ. The normalized adjacency matrix of the Cayley graph associated to g_{1}, …, g_{k} ∈ Γ is given by

A(g_{1}, …, g_{k}) =^{def} \frac{1}{2k} ∑_{i=1}^{k} (R(g_{i}) + R(g_{i}^{−1})) .  (3)

In order to apply Lemma 1.4, we are therefore interested in the random quantity

∥∑_{i=1}^{k} (I − \frac{1}{n}J) \frac{R(g_{i}) + R(g_{i}^{−1})}{2k}∥_{S_{p}} .  (4)

All the known proofs of the Alon–Roichman theorem, corresponding to the case p = ∞ in (4), proceed by proving the desired deviation inequality for operator-valued random variables; the original proof of Alon and Roichman uses the Wigner semicircle method, while later proofs rely on the Ahlswede–Winter matrix valued deviation bound [1]. Alternatively, one can use in this context the moment inequalities arising from the non-commutative Khinchine inequalities of Lust-Piquard and Pisier [15, 16], and this method also yields the inequalities that we need for the deviation of the Schatten p-norm in (4). Nevertheless, all of these approaches are specific to operator-valued random variables, and are deeper than the simple argument that we present below. It turns out that for our purposes, it suffices to use an elementary geometric argument that ignores the specific structure of matrix spaces—it works for random variables taking values in arbitrary uniformly smooth normed spaces, of which the Schatten p-norms are a special case.

For a Banach space (X, ∥·∥), the triangle inequality implies that ∥x+τy∥+∥x−τy∥ ⩽ 2+2τ for every two unit vectors x, y ∈ X and every τ > 0. X is said to be uniformly smooth if ∥x + τy∥ + ∥x − τy∥ ⩽ 2 + o(τ), where the o(τ) term is independent of the choice of unit vectors x, y ∈ X. Formally, consider the following quantity, called the modulus of uniform smoothness of X.

ρ_{X}(τ) =^{def} sup \{\frac{∥x + τy∥ + ∥x − τy∥}{2} − 1 : x, y ∈ X, ∥x∥ = ∥y∥ = 1\} .  (5)

Then X is uniformly smooth if lim_{τ→0} \frac{ρ_{X}(τ)}{τ} = 0.

X is said to have a modulus of smoothness of power type 2 if there exists s > 0 such that for all τ > 0 we have ρ_{X}(τ) ⩽ sτ^{2}. For simplicity, we will only deal here with spaces that have a modulus of smoothness of power type 2. All of our results below carry over, with obvious modifications, to general uniformly smooth spaces (of course, in this more general setting, the probabilistic bounds that we get will no longer be sub-Gaussian). For concreteness, if p ⩾ 2 and S_{p} denotes the space of all n × n matrices equipped with the Schatten p-norm, then for every τ > 0 we have ρ_{S_{p}}(τ) ⩽ \frac{p−1}{2}τ^{2}. The fact that the modulus of smoothness of S_{p} has power type 2 when p ⩾ 2 was first proved by Tomczak-Jaegermann in [20]. The exact modulus of smoothness of S_{p} was computed in [6]. The case of L_{p}(μ) spaces is much older—the modulus of smoothness in this case was computed by Hanner in [10].

An Azuma-type deviation inequality holds for general norms whose modulus of smoothness has power type 2.

Theorem 1.5. There exists a universal constant c ∈ (0, ∞) with the following property. Fix s > 0 and assume that a Banach space (X, ∥ · ∥) satisfies ρ_{X}(τ) ⩽ sτ^{2} for all τ > 0. Fix also a sequence of positive numbers {a_{k}}_{k=1}^{∞} ⊆ (0, ∞). Let {M_{k}}_{k=1}^{∞} ⊆ X be an X-valued martingale satisfying the pointwise bound ∥M_{k+1} − M_{k}∥ ⩽ a_{k} for all k ∈ ℕ. Then for every u > 0 and k ∈ ℕ we have

ℙ [∥M_{k+1} − M_{1}∥ ⩾ u] ⩽ e^{s+2} · exp (−\frac{cu^{2}}{a_{1}^{2} + ⋯ + a_{k}^{2}} ) .  (6)

Theorem 1.5 is a consequence of well understood moment inequalities in Banach space theory. The key insights here are due to the work of Pisier. Theorem 1.5 relies on an estimate of implicit constants appearing in Pisier’s inequality [18]; this is done in Section 2. While these bounds are not available in [18], undoubtedly Pisier could have computed them if they were needed for the purpose of his investigations in [18]. Therefore, Section 2 should be viewed as mainly expository. In addition to obtaining the estimates that we need, another purpose of Section 2 is to present the proof in a way which highlights the clarity and simplicity of the general geometric argument leading to Theorem 1.5.

Note that the exponential dependence on s in (6) cannot be improved. A roundabout way to see this is to note that when X is the space of n × n matrices equipped with the Schatten p norm, then since in this case s ⩽ p/2, and for p = log n we have ∥ · ∥_{S_{p}} ≍ ∥ · ∥_{S_{∞}} (= the operator norm), the inequality (6) corresponds (for this value of p) to the Ahlswede–Winter deviation inequality used in [11, 8, 22] to prove the (sharp) logarithmic dependence of k on n in the Alon–Roichman theorem. For random variables taking values in the space of matrices equipped with the operator norm, deeper methods lead to results that are more refined than Theorem 1.5, but do not have an interpretation in the setting of general uniformly smooth Banach spaces, and are not needed for our purposes; see [21] for more information on this topic.

2. The Azuma inequality in uniformly smooth normed spaces

Our main result is the following theorem.

Theorem 2.1. Fix s > 0 and q ⩾ 2. Assume that a Banach space X satisfies ρ_{X}(τ) ⩽ sτ^{2} for all τ > 0. Let {Z_{n}}_{n=1}^{∞} be X-valued random variables such that for all n ∈ N we have 𝔼 [∥Z_{n}∥^{q}] < ∞. Denote S_{n} = Z_{1} + ⋯ + Z_{n}. Assume that for all n ∈ ℕ we have

𝔼 [∥S_{n} − Z_{n+1}∥^{q}] ⩾ 𝔼 [∥S_{n}∥^{q}] .  (7)

Then

(𝔼 [∥S_{n}∥^{q}] )^{1/q} ⩽ 8\sqrt{s + q} · \sqrt{∑_{j=1}^{n} (𝔼 [∥Z_{j}∥^{q}])^{2/q}}.  (8)

Before proving Theorem 2.1 we record two concrete examples. The most important case is when {Z_{n}}_{n=1}^{∞} form a martingale difference sequence. In other words, there exists a filtration ℱ_{1} ⊆ ℱ_{2} ⊆ ⋯ such that Z_{1}, …, Z_{n} are measurable with respect to ℱ_{n} for all n ∈ ℕ, and for m > n we have 𝔼 [Z_{m}|ℱ_{n}] = 0. In this case, using the notation of Theorem 2.1 and the convexity of the norm, we see that

𝔼 [∥S_{n} − Z_{n+1}∥^{q}|ℱ_{n}] ⩾ ∥𝔼 [S_{n} − Z_{n+1}|ℱ_{n}] ∥^{q} = ∥S_{n}∥^{q}.  (9)

By taking expectation we get that the assumption (7) is satisfied.

Another example worth mentioning is when q is an even integer and Z_{n} ∈ L_{q}(Ω, μ) satisfy the point-wise condition 𝔼 [Z_{n+1}S_{n}^{q−1}] ⩽ 0 for all n ∈ ℕ. In this case

𝔼 [∥S_{n} − Z_{n+1}∥_{L_{q}(Ω,μ)}^{q}] = 𝔼 [∫_{Ω}(S_{n} − Z_{n+1})^{q}dμ]

⩾ 𝔼 [∫_{Ω} (S_{n}^{q} − qZ_{n+1}S_{n}^{q−1}) dμ] ⩾ 𝔼 [∥S_{n}∥_{L_{q}(Ω,μ)}^{q}] .

Therefore the assumption (7) holds in this case.

Proof of Theorem 1.5. An application of Theorem 2.1 to Z_{n} = M_{n+1} − M_{n}, together with Markov’s inequality, shows that for all q ⩾ max{2, s} and u > 0,

ℙ [∥M_{k+1} − M_{1}∥ ⩾ u] ⩽ (\frac{16\sqrt{q(a_{1}^{2} + ⋯ + a_{k}^{2})}}{u})^{q} .  (10)

The optimal choice of q in (10) is q = \frac{u^{2}}{256e(a_{1}^{2}+···+a_{k}^{2})}, which is an allowed value of q provided u^{2} ⩾ max{s, 2} · 256e(a_{1}^{2} + ⋯ + a_{k}^{2}). This implies (6). □

We now pass to the proof of Theorem 2.1. We start with the following lemma, whose proof is a slight variant of the proof of Proposition 7 in [6].

Lemma 2.2. Assume that ρ_{X}(τ) ⩽ sτ^{2} for all τ > 0. Then for every x, y ∈ X and for every q ⩾ 2 we have

\frac{∥x + y∥^{q} + ∥x − y∥^{q}}{2} ⩽ (∥x∥^{2} + 8(s + q) · ∥y∥^{2})^{q/2} .  (11)

Proof. Assume first of all that ∥x∥ = 1 and ∥y∥ ⩽ 1. Denote

b =^{def} \frac{∥x + y∥ + ∥x − y∥}{2} and β =^{def} \frac{∥x + y∥ − ∥x − y∥}{∥x + y∥ + ∥x − y∥}.

Then b ⩾ 1, since the function τ ↦ ∥x + τy∥ + ∥x − τy∥ is convex and even, and hence attains its minimum at τ = 0. Also, the triangle inequality implies that β ⩽ \frac{∥y∥}{b} ⩽ ∥y∥ ⩽ 1. If we write

(\frac{(1 + β)^{q} + (1 − β)^{q}}{2} )^{1/q} = 1 + θ

then θ ∈ [0, 1] and θ ⩽ (q − 1)β^{2}. Both of these inequalities are elementary numerical facts; the proof of the latter inequality can be found in many places, e.g., [13, Lem. 1.e.14].

Now,

(\frac{∥x + y∥^{q} + ∥x − y∥^{q}}{2} )^{1/q} = b (\frac{(1 + β)^{q} + (1 − β)^{q}}{2} )^{1/q} ⩽^{(♣)} [1 + ρ_{X}(∥y∥)] · [1 + θ]

⩽^{(♣♣)} \sqrt{1 + 8 [ρ_{X}(∥y∥) + θ]} ⩽ \sqrt{1 + 8(s + q)∥y∥^{2}},

where in (♣) we used the definition of ρ_{X} and θ and in (♣♣) we used the elementary inequality (1 + u)(1 + v) ⩽ \sqrt{1 + 8(u + v)}, which is valid for all u, v ∈ [0, 1]. This proves the assertion of Lemma 2.2 when ∥y∥ ⩽ ∥x∥. When ∥y∥ ⩾ ∥x∥ apply the same reasoning with the roles of x and y reversed, and use the bound ∥y∥^{2} +8(s+q)·∥x∥^{2} ⩽ ∥x∥^{2} +8(s+q)·∥y∥^{2}. □

In what follows, if (Ω, μ) is a measure space then L_{q}(X, Ω, μ) will denote the Banach space of all functions f : Ω → X such that

∥f∥_{L_{q}(X,Ω,μ)}^{q} =^{def} ∫_{Ω} ∥f∥^{q}dμ < ∞.

In [9] it is shown that if q ⩾ 2 and X is 2-smooth then L_{q}(X, Ω, μ) is also 2-smooth. The dependence of the modulus of smoothness of L_{q}(X, Ω, μ) on q and the modulus of smoothness of X can be deduced from the proofs in [9], but is not stated there explicitly. This dependence is crucial for us, so we will now show how it easily follows from Lemma 2.2.

Corollary 2.3. Assume that ρ_{X}(τ) ⩽ sτ^{2} for all τ > 0. Then ρ_{L_{q}(X,Ω,μ)}(τ) ⩽ 4(s + q)τ^{2} for every τ > 0.

Proof. Fix f, g ∈ L_{q}(X, Ω, μ) with ∥f∥_{L_{q}(X,Ω,μ)} = ∥g∥_{L_{q}(X,Ω,μ)} = 1 and τ > 0. Then,

(\frac{∥f + τg∥_{L_{q}(X,Ω,μ)} + ∥f − τg∥_{L_{q}(X,Ω,μ)}}{2} )^{q} ⩽ \frac{∥f + τg∥_{L_{q}(X,Ω,μ)}^{q} + ∥f − τg∥_{L_{q}(X,Ω,μ)}^{q}}{2}
= ∫_{Ω} \frac{∥f + τg∥^{q} + ∥f − τg∥^{q}}{2} dμ
⩽^{(∗)} ∫_{Ω} (∥f∥^{2} + 8(s + q) · τ^{2}∥g∥^{2})^{q/2} dμ
⩽^{(∗∗)} (∥f∥_{L_{q}(X,Ω,μ)}^{2} + 8(s + q)τ^{2}∥g∥_{L_{q}(X,Ω,μ)}^{2})^{q/2}
= (1 + 8(s + q)τ^{2})^{q/2} ,  (12)

where in (∗) we used Lemma 2.2 and in (∗∗) we used the triangle inequality in L_{q/2}(Ω, μ). It follows from (12) that

\frac{∥f + τg∥_{L_{q}(X,Ω,μ)} + ∥f − τg∥_{L_{q}(X,Ω,μ)}}{2} ⩽ \sqrt{1 + 8(s + q)τ^{2}} ⩽ 1 + 4(s + q)τ^{2}.  □

The following lemma goes back to [12, 7] (see also Proposition 2.2 in [18]).

Lemma 2.4. Assume that ρ_{X}(τ) ⩽ sτ^{2} for all τ > 0. Let {x_{n}}_{n=1}^{∞} ⊆ X be a sequence of vectors in X and for every n ∈ ℕ denote S_{n} = x_{1} + ⋯ + x_{n}. Assume that for all n ∈ ℕ we have ∥S_{n} − x_{n+1}∥ ⩾ ∥S_{n}∥. Then for every n ∈ ℕ,

∥S_{n}∥^{2} ⩽ 10(s + 2) (∥x_{1}∥^{2} + ⋯ + ∥x_{n}∥^{2}) .

Proof. Apply Lemma 2.2 with q = 2, x = S_{n} and y = x_{n+1} to get that

\frac{∥S_{n+1}∥^{2} + ∥S_{n}∥^{2}}{2} ⩽^{(⋆)} \frac{∥S_{n} + x_{n+1}∥^{2} + ∥S_{n} − x_{n+1}∥^{2}}{2} ⩽ ∥S_{n}∥^{2} + 5(s + 2)∥x_{n+1}∥^{2}, (13)

where in (⋆) we used the assumption ∥S_{n} − x_{n+1}∥ ⩾ ∥S_{n}∥. Inequality (13) is equivalent to ∥S_{n+1}∥^{2} ⩽ ∥S_{n}∥^{2} + 10(s + 2)∥x_{n+1}∥^{2}. Therefore Lemma 2.4 follows by induction. □

Proof of Theorem 2.1. Let (Ω, μ) be the probability space on which the random variables {Z_{n}}_{n=1}^{∞} are defined. Lemma 2.4 applied to the Banach space X′ = L_{q}(X, Ω, μ), combined with Corollary 2.3, implies Theorem 2.1. □

Remark 2.1. Readers who are mainly interested in the case of operator valued random variables should note that the above argument proves the general Azuma inequality (6) in a self-contained way, except that we quoted the fact that ρ_{S_{p}}(τ) ≲ pτ^{2}. We wish to stress that the proof of this fact is elementary and accessible to non-experts. When p = 2k is an even integer, the sharp estimate on the modulus of smoothness of S_{p} was proved in [20] by expanding the quantity ∥A + B∥_{S_{p}}^{p} + ∥A − B∥_{S_{p}}^{p} = trace ([(A + B)(A^{∗} + B^{∗})]^{k} + [(A − B)(A^{∗} − B^{∗})]^{k}), and estimating the summands in the resulting sum separately. When p ⩾ 2 is not an even integer, the computation of the sharp modulus of smoothness of S_{p} in [6] is more subtle, but still elementary. Note that for the purpose of our application to small-set expansion of graphs, the case of even p suffices. Also, in the case of S_{p}, the above proof is much shorter (yielding better constants), since the intermediate steps of Lemma 2.2 and Corollary 2.3 are not needed—the inequalities obtained in Lemma 2.2 and Corollary 2.3 are the way that ρ_{S_{p}}(τ) was estimated in [20, 6] in the first place. The role of these elementary intermediate steps is only to relate the standard definition (5) of the modulus of uniform smoothness to inequalities such as (11), but in the literature, when one estimates ρ_{X}(τ), this is often done by proving (11) directly.

3. Schatten norm bounds and graph expansion

Let G = (V, E) be an n-vertex d-regular graph. For p ⩾ 1, the normed space L_{p}(V) is the space of all x ∈ ℂ^{V}, equipped with the norm

∥x∥_{L_{p}(V)} =^{def} (\frac{1}{n} ∑_{u∈V} |x(u)|^{p})^{1/p} .

In what follows, whenever we refer to an orthornormal eigenbasis e_{1}, …, e_{n} of the normalized adjacency matrix A(G), it will always be understood that it is orthonormal in L_{2}(V), the eigenvectors are indexed so that A(G)e_{j} = λ_{j}(G)e_{j} for all j ∈ {1, …, n}, and e_{1} = 1_{V} (the constant 1 function).

The following lemma becomes Lemma 1.4 when q = r = ∞.

Lemma 3.1. Assume that p, r > 1 and q > \frac{2p}{p−1}. Let G = (V, E) be an n-vertex d-regular graph, and let e_{1}, …, e_{n} be an orthonormal eigenbasis of the normalized adjacency matrix A(G). Then for every ∅ ≠ S ⊊ V we have,

| \frac{e_{G}(S, V ∖ S)}{\frac{d}{n}|S|(n − |S|)} − 1| ⩽ M^{\frac{q}{p(q−2)}} (∑_{i=2}^{n} |λ_{i}(G)|^{p})^{\frac{1}{p}} (\frac{|S|^{δ}(n − |S|)^{1−δ} + |S|^{1−δ}(n − |S|)^{δ}}{n} )^{\frac{1}{1−δ}} ,

where

M =^{def} (∑_{j=1}^{n} ∥e_{j}∥_{L_{r}(V)}^{q})^{1/q} and δ =^{def} \frac{q(r − 2)}{pr(q − 2) + q(r − 2)}.  (14)

Proof. Consider the linear operator T : ℂ^{V} → ℂ^{n} given by

T (x) =^{def} (⟨x, e_{1}⟩, ⟨x, e_{2}⟩, …, ⟨x, e_{n}⟩).

Since {e_{1}, …, e_{n}} is an orthonormal basis of L_{2}(V) we have ∥T (x)∥_{ℓ_{2}^{n}} = ∥x∥_{L_{2}(V)} for all x ∈ ℂ^{V}. Moreover, using Hölder’s inequality we have

∥T (x)∥_{ℓ_{q}^{n}} = (∑_{j=1}^{n} |⟨x, e_{j}⟩|^{q})^{1/q} ⩽ (∑_{j=1}^{n} ∥e_{j}∥_{L_{r}(V)}^{q}∥x∥_{L_{\frac{r}{r−1}} (V)}^{q})^{1/q} = M∥x∥_{L_{\frac{r}{r−1} (V )}}.

In other words, we have the operator norm bounds

∥T ∥_{L_{2}(V)→ℓ_{2}^{n}} = 1 and ∥T ∥_{L_{\frac{r}{r−1}} (V)→ℓ_{q}^{n}} ⩽ M.

Recall that \frac{2p}{p−1} ∈ (2, q), so we can define ε ∈ (0, 1) by \frac{p−1}{2p} = \frac{ε}{2} + \frac{1−ε}{q}, i.e.,

ε = 1 − \frac{q}{p(q − 2)}.

If we then define a > 1 via \frac{1}{a} = \frac{ε}{2} + \frac{(1−ε)(r−1)}{r}, i.e.,

a = \frac{2pr(q − 2)}{pr(q − 2) + q(r − 2)} =^{(14)} 2(1 − δ),

then the Riesz–Thorin interpolation theorem (see [23, Ch. XII]) asserts that for every x ∈ ℂ^{V} we have

∥T (x)∥_{ℓn ; \frac{2p}{p−1}} ⩽ M^{1−ε}∥x∥_{L_{a}(V)} = M^{\frac{q}{p(q−2)}} ∥x∥_{L_{a}(V)}.  (15)

Fix S ⊆ V and consider the function x ∈ ℂ^{V} given by

x =^{def} (n − |S|)1_{S} − |S|1_{V ∖S}.

Since ⟨x, e_{1}⟩ = ∑_{u∈V} x(u) = 0, the bound (15) becomes

(∑_{j=2}^{n} |⟨x, e_{j}⟩|^{\frac{2p}{p−1}} )^{\frac{p−1}{2p}} ⩽ M^{\frac{q}{p(q−2)}} (\frac{|S|(n − |S|)^{a} + (n − |S|)|S|^{a}}{n} )^{\frac{1}{a}} .

Hence,

|⟨A(G)x, x⟩| = |∑_{j=2}^{n} λ_{j}(G)⟨x, e_{j}⟩^{2}| ⩽ (∑_{j=2}^{n} |λ_{j}(G)|^{p})^{\frac{1}{p}} (∑_{j=2}^{n} |⟨x, e_{j}⟩|^{\frac{2p}{p−1}} )^{\frac{p−1}{p}}

⩽ M^{\frac{2q}{p(q−2)}} (∑_{j=2}^{n} |λ_{j}(G)|^{p})^{\frac{1}{p}} (\frac{|S|(n − |S|)^{a} + (n − |S|)|S|^{a}}{n} )^{\frac{2}{a}} .

The required result now follows from the identity

⟨A(G)x, x⟩ = |S|(n − |S|) − \frac{n}{d}e_{G}(S, V ∖ S).  □

4. Proof of Theorem 1.2

Let Γ be a group of cardinality n. Recall that R : Γ → GL(L_{2}(Γ)) is the right regular representation, and given g_{1}, …, g_{k} ∈ Γ, the matrix A(g_{1}, …, g_{k}) is defined as in (3).

Lemma 4.1. There exists a universal constant C ∈ (0, ∞) with the following property. Fix k, n ∈ ℕ and a group Γ of cardinality n. Let g_{1}, …, g_{k} ∈ Γ be chosen independently and uniformly at random. Then with probability at least \frac{1}{2}, for every integer p ⩾ 2 we have

∥(I − \frac{1}{n}J) A(g_{1}, …, g_{k})∥_{S_{p}} ⩽ Cn^{1/p}\sqrt{\frac{p}{k}}.

Proof. For all i ∈ \{1, …, k\}, since 𝔼 [R(g_{i})] = 𝔼 [R(g_{i}^{−1})] = \frac{J}{n}, we have

𝔼 [(I − \frac{J}{n}) \frac{R(g_{i}) + R(g_{i}^{−1})}{2}] = 0.  (16)

Moreover, note that we have ∥(I − \frac{1}{n}J) R(g_{i})∥_{S_{p}} = (n − 1)^{1/p}, because MM^{∗} = I − \frac{1}{n}J, where M = (I − \frac{1}{n}J) R(g_{i}). We therefore have the (point-wise) bound

∥(I − \frac{1}{n}J) \frac{R(g_{i}) + R(g_{i}^{−1})}{2}∥_{S_{p}} ⩽ (n − 1)^{1/p}.  (17)

Theorem 2.1 now implies that for some universal constant c ∈ (0, ∞),

𝔼 [∥(I − \frac{1}{n}J) A(g_{1}, …, g_{k})∥_{S_{p}}^{p}] ⩽ (\frac{cp}{k})^{p/2} n.

Hence,

𝔼 [∑_{p=2}^{∞} (\frac{∥(I − \frac{1}{n}J) A(g_{1}, …, g_{k})∥_{S_{p}}}{2n^{1/p}\sqrt{cp/k}} )^{p}] ⩽ ∑_{p=2}^{∞} \frac{1}{2^{p}} = \frac{1}{2}.

It follows from Markov’s inequality that with probability at least \frac{1}{2} we have

max_{p∈ℕ∩[2,∞)} (\frac{∥(I − \frac{1}{n}J) A(g_{1}, …, g_{k})∥_{S_{p}}}{2n^{1/p}\sqrt{cp/k}} )^{p} ⩽ ∑_{p=2}^{∞} (\frac{∥(I − \frac{1}{n}J) A(g_{1}, …, g_{k})∥_{S_{p}}}{2n^{1/p}\sqrt{cp/k}} )^{p} ⩽ 1. □

Proof of Theorem 1.2. Γ is now Abelian, and therefore for every g_{1}, …, g_{k} ∈ Γ, the characters of Γ are an orthonormal eigenbasis of A(g_{1}, …, g_{k}), consisting of functions whose absolute value is point-wise bounded by 1. By Lemma 3.1 and Lemma 4.1, with probability at least \frac{1}{2} over i.i.d. uniform choice of g_{1}, …, g_{k} ∈ Γ, if we let G be the Alon–Roichman graph whose adjacency matrix is A(g_{1}, …, g_{k}), then every S ⊆ Γ with 2 ⩽ |S| ⩽ \frac{n}{2} satisfies

| \frac{e_{G}(S, V ∖ S)}{\frac{2k}{n}|S|(n − |S|)} − 1| ≲ min_{p∈ℕ∩[2,∞)} (n^{\frac{1}{p}} \sqrt{\frac{p}{k}} (\frac{|S|^{\frac{1}{p+1}} (n − |S|)^{\frac{p}{p+1}} + |S|^{\frac{p}{p+1}} (n − |S|)^{\frac{1}{p+1}}}{n} )^{\frac{p+1}{p}} )

≲ min_{p∈ℕ∩[2,∞)} (|S|^{\frac{1}{p}} \sqrt{\frac{p}{k}}) ≲ \sqrt{\frac{log |S|}{k}}, (18)

where in the last step of (18) we choose p = 2⌈log |S|⌉. □

5. Proof of Theorem 1.3

If k ⩽ 1/ε^{2} then Theorem 1.3 is vacuous for c > 0 small enough. Assuming k ⩾ 1/ε^{2}, denote p = 2ε^{2}k ⩾ 2. Arguing analogously to (18), we see that there exists a universal constant K ∈ (0, ∞) such that with probability at least \frac{1}{2} over i.i.d. uniform choice of g_{1}, …, g_{k} ∈ Γ, if we let G be the Alon–Roichman graph whose adjacency matrix is A(g_{1}, …, g_{k}), then for all S ⊆ Γ with 2 ⩽ |S| ⩽ \frac{n}{2},

| \frac{e_{G}(S, V ∖ S)}{\frac{2k}{n}|S|(n − |S|)} − 1| ⩽ K|S|^{\frac{1}{p}} \sqrt{\frac{p}{k}} = εK\sqrt{2}|S|^{\frac{1}{2ε^{2}k}} ⩽ 2Kε,

provided |S| ⩽ 2^{ε^{2}k}. □

References

[1] R. Ahlswede and A. Winter. Strong converse for identification via quantum channels. IEEE Trans.

Inform. Theory, 48(3):569–579, 2002.

[2] N. Alon and V. D. Milman. λ_{1}, isoperimetric inequalities for graphs, and superconcentrators. J. Combin.

Theory Ser. B, 38(1):73–88, 1985.

[3] N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures Algorithms,

5(2):271–284, 1994.

[4] N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics

and Optimization. Wiley-Interscience [John Wiley & Sons], New York, second edition, 2000. With an

appendix on the life and work of Paul Erdős.

[5] S. Arora, B. Barak, and D. Steurer. Subexponential algorithms for Unique Games and related problems.

To appear in proceedings of 51th Annual IEEE Symposium on Foundations of Computer Science, 2010.

[6] 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.

[7] Buĭ-Min-Či and V. I. Gurariĭ. Certain characteristics of normed spaces and their application to the

generalization of Parseval’s equality to Banach spaces. Teor. Funkciĭ Funkcional. Anal. i Priložen.

Vyp., 8:74–91, 1969.

[8] D. Christofides and K. Markström. Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales. Random Structures Algorithms, 32(1):88–100, 2008.

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

[10] O. Hanner. On the uniform convexity of L^{p} and l^{p}. Ark. Mat., 3:239–244, 1956.

[11] Z. Landau and A. Russell. Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem. Electron. J. Combin., 11(1):Research Paper 62, 6 pp. (electronic), 2004.

[12] J. Lindenstrauss. On the modulus of smoothness and divergent series in Banach spaces. Michigan Math. J., 10:241–252, 1963.

[13] J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. II, volume 97 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas]. Springer-Verlag, Berlin, 1979. Function spaces.

[14] P.-S. Loh and L. J. Schulman. Improved expansion of random Cayley graphs. Discrete Math. Theor. Comput. Sci., 6(2):523–528 (electronic), 2004.

[15] F. Lust-Piquard. Inégalités de Khintchine dans C_{p} (1 < p < ∞). C. R. Acad. Sci. Paris Sér. I Math., 303(7):289–292, 1986.

[16] F. Lust-Piquard and G. Pisier. Noncommutative Khintchine and Paley inequalities. Ark. Mat., 29(2):241–260, 1991.

[17] I. Pak. Random Cayley graphs with O(log |G|) generators are expanders. In Algorithms—ESA ’99 (Prague), volume 1643 of Lecture Notes in Comput. Sci., pages 521–526. Springer, Berlin, 1999.

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

[19] R. M. Tanner. Explicit concentrators from generalized N-gons. SIAM J. Algebraic Discrete Methods, 5(3):287–293, 1984.

[20] N. Tomczak-Jaegermann. The moduli of smoothness and convexity and the Rademacher averages of trace classes S_{p}(1 ⩽ p < ∞). Studia Math., 50:163–182, 1974.

[21] J. Tropp. User-friendly tail bounds for matrix martingales. Preprint available at

http://arxiv.org/abs/1004.4389, 2010.

[22] A. Wigderson and D. Xiao. Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. Theory Comput., 4:53–76, 2008.

[23] A. Zygmund. Trigonometric series. Vol. I, II. Cambridge Mathematical Library. Cambridge University Press, Cambridge, third edition, 2002. With a foreword by Robert A. Fefferman.

Courant Institute, 251 Mercer Street, New York, NY 10012, USA.

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