On the Second Eigenvalue of Hypergraphs

Joel Friedman^{∗} Dept. of Comp. Sci. Princeton University Princeton, NJ 08544

Avi Wigderson Dept. of Comp. Sci. Hebrew University Jerusalem 91904 ISRAEL

November 11, 1989

1 The Second Eigenvalue of a Hypergraph

In this section we will first define the second eigenvalue of 3-uniform hypergraph, and then discuss the general notion, as it applies to other uniform hypergraphs and graphs. To motivate our definition, notice that if G is an undirected d-regular graph, i.e. each vertex has degree d, then the second largest eigenvalue in absolute value, λ_{2}, of G’s adjacency matrix, A, satisfies

|λ_{2}| = ∥A − \frac{d}{n} ( \begin{matrix}1 & ⋯ & 1 \\ ⋮ & ... & ⋮ \\ 1 & ⋯ & 1 \end{matrix} )∥_{L^{2}(V)} ,

where n = |V |.

Let G = (V, E) be a 3-uniform hypergraph; i.e. E is a subset of subsets of V of size 3. We consider the space, L^{2}(V), of real valued functions on V with the usual inner product; let e_{1},…, e_{n} be the standard basis for L^{2}(V), where e_{i} takes the value 1 on the i-th vertex of V and 0 elsewhere. It is natural to construct from G a trilinear form, that is a map from τ, mapping triples of vectors in L^{2}(V) to R, namely

τ (∑_{i=1}^{n} α_{i}e_{i}, ∑_{j=1}^{n} β_{j}e_{j}, ∑_{k=1}^{n} γ_{k}e_{k}) = ∑_{i,j,k} α_{i}β_{j}γ_{k}τ_{i,j,k}

∗The author wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR–8858788, and the Office of Naval Research under Grant N00014–87–K–0467.

where

τ_{i,j,k} = \{ \begin{matrix}1 & if \{i, j, k\} ∈ E \\ 0 & otherwise \end{matrix}

Let 1 denote the all 1’s vector, and let 1 ⊗1 ⊗1 denote the all 1’s trilinear form (i.e. the form ν defined as τ but with ν_{i,j,k} = 1 for all i, j, k). We define τ to be d-regular if

σ = τ − \frac{d}{n}1 ⊗ 1 ⊗ 1

has the property that

σ(1, u, v) = σ(u,1, v) = σ(u, v,1) = 0

for all u and v. In this case we define the second eigenvalue of G (and τ) to be

λ_{2} = ∥σ∥_{L^{2}(V)} = sup_{∥u∥=∥v∥=∥w∥=1} |σ(u, v, w)|.

We pause for a few remarks. First of all, for simplicity we have abused some of the usual tensor conventions; in particular, we will often identify spaces and elements of spaces with their duals implicitly when the distinction serves no purpose and/or needlessly complicates the notation or discussion. For example, the all 1’s trilinear form is really the dual of 1 ⊗ 1 ⊗ 1 in the usual conventions.

Second, just as ordinary directed graphs can have multiple edges and self-loops, we can accomodate such notions here. If an edge {i, j, k} occurs with multiplicity m, then the six corresponding entries of τ will have an m instead of a 1. Also, an edge which is a self-loop, {i, i, i}, should contribute 6 to τ_{i,i,i}, on the principle that the contribution should be determined so that each edge contributes a total of 6 to all the entries of τ. Similarly an edge, {i, i, j} should contribute 2 to each of τ_{i,i,j}, τ_{i,j,i}, and τ_{j,i,i}.

Thirdly, we can also handle the notion of directed edges. We say that a directed 3-uniform hypergraph is a hypergraph where each edge {i, j, k} has a specified order; equivilently, E is a subset of V × V × V. Now the trilinear form τ is defined by τ_{i,j,k} being the multiplicity of the edge (i, j, k). From a directed hypergraph we can form an undirected hypergraph, i.e. the usual notion of hypergraph, by forgetting about the ordering on the edges. The new trilinear form is the symmetrized version of the old one. This also explains why undirected degenerate edges such as {i, i, i} should contribute 6 to τ_{i,i,i} in the usual (undirected) notion of hypergraph. Identifying a hypergraph with its trilinear form, we can think of undirected hypergraphs as special cases of directed hypergraphs.

Fourth, we define for any trilinear form on L^{2}(V), μ, its first eigenvalue to be its norm with respect to L^{2}(V), i.e.

λ_{1}(μ) = ∥μ∥_{L^{2}(V)} = sup_{∥u∥=∥v∥=∥w∥=1} |μ(u, v, w)|.

If u, v, w is a triple achieving the above sup, we shall call (u, v, w) or u × v × w an eigenvector. We can also define d-regular for a general trilinear form as above, and therefore extend the notion of second eigenvalue to directed hypergraphs. It is easy to check that an undirected hypergraph is d-regular if for every vertices i, j, there are exactly d vertices k for which {i, j, k} is an edge (with the case i = j included); similarly, a directed hypergraph is d-regular if for every vertices i, j there are d edges of each of the forms (i, j, ·), (i, ·, j), and (·, i, j).

Fifth, it becomes clear how we want to define the second eigenvalue in the more general case. For any sets, V_{1},…, V_{k}, we define the first eigenvalue of a k-linear form mapping V_{1} × ⋯ × V_{k} to R as its norm with respect to the norms L^{2}(V_{i}). A k-linear form, τ, is d-regular if

σ = τ − \frac{d}{n}1_{V_{1}} ⊗ ⋯ ⊗ 1_{V_{k}},

with n being the largest among the |V_{i}|’s, satisfies

σ(v_{1},…, v_{k}) = 0

whenever some v_{i} is 1_{V_{i}}. In this case we define the second eigenvalue of τ to be λ_{1}(σ). Notice that for a directed graph, with adjacency matrix A, which is d-regular, it’s second eigenvalue in the new sense is the square root of the (classical) second largest eigenvalue of AA^{T}.

Sixth, the first and second eigenvalue of multilinear forms as defined above are always non-negative numbers. While much of the literature on graphs considers the second eigenvalue as the eigenvalue with the second largest absolute value, sometimes one simply considers the second largest (positive) eigenvalue. Here the distinction is lost.

Lastly, we could define the eigenvalues and/or norms of multilinear forms with respect to other norms on the space of functions on V, such as L^{p}(V) for any 1 ≤ p ≤ ∞. In the applications we have in mind, it does not seem to help to consider the other norms; and, in fact, one can say more about the L^{2}(V) norms than for other values of p.

We return to the discussion of 3-uniform hypergraphs. There is a lot of structure for graphs that we don’t know how to carry over to 3-uniform hypergraphs. For example, we don’t know how multiply two hypergraphs. However, a fair amount of the theory for graphs can be generalized to 3-uniform hypergraphs. We will prove:

Theorem 1.1 The first eigenvalue of a d-regular 3-uniform hypergraph is dn^{1/2}; i.e. the associated trilinear form τ is maximized on (1,1,1).

Theorem 1.2 A symmetric trilinear form τ has a unit vector v such that ∥τ∥ = |τ(v, v, v)|.

Theorem 1.3 Every 3-uniform, d-regular hypergraph has second eigenvalue ≥ \sqrt{d(n − d)/n}.

Next we’d like to prove a theorem about random hypergraphs. For graphs there are probability spaces of random d-regular graphs that are easy to work with. For hypergraphs the situation is more complicated. It becomes convenient to weaken the requirement of d-regularity. For any trilinear form, τ, we define its second eigenvalue with respect to d-regularity to be

λ_{2,d}(τ) ≡ ∥τ − \frac{d}{n}1 ⊗ 1 ⊗ 1∥.

Theorem 1.4 For any C there is a C′ such that for any n and d ≥ C′ log n, a random 3-uniform hypergraph on n vertices with dn^{2} edges chosen randomly has second eigenvalue ≤ C′(log n)^{3/2}\sqrt{d} with probability ≥ 1 − n^{−C min(\sqrt{d},n^{1/6})}.

All of the above theorems have generalizations to t-uniform hypergraphs. Theorems 1.1, 1.2, and 1.3 hold as is for t-uniform hypergraphs with t > 3. The analog of theorem 1.4 for t ≥ 3 is:

Theorem 1.5 For any n, d ≥ Ct log n, a random t-uniform hypergraph on n vertices with dn^{t−1} edges chosen randomly has second eigenvalue ≤ (C log n)^{t/2}\sqrt{d} with probability at least 1 − n^{−C′min(\sqrt{d},n^{1/(t+3)})/t}.

We remark that presumably with more work, one could replace t/2 in the above exponent of log n in the eigenvalue estimate with (t − 2)/2 (see the end of section 6). In our applications the log n factors are unimportant.

We do not know, at present, how to explicitly construct hypergraphs to match the bounds in theorem 1.5. However, it is easy to construct graphs with λ_{1} and λ_{2} separated. Let G = (V, E) be any graph which is d-regular, and let G̃ = (V, V^{t−2}×E). It is easy to see that λ_{2}(G̃) ≤ n^{(t−2)/2}λ_{2}(G).

To achieve smaller λ_{2}, we generalize the notion of Cayley graphs to hypergraphs. Let G be a finite group, and H a symmetric set of generators. Then the t-uniform Cayley hypergraph on G and H, has vertex set G and edges

E = {(x_{1},…, x_{t}) : x_{1} ⋯ x_{t} ∈ H}.

We can calculate the eigenvalues of the t-uniform Cayley hypergraph from those of the Cayley graph and a knowledge of the decomposition of L^{2}(G) under the right regular representation. While most explicit constructions of graphs with essentially optimal λ_{2} are Cayley graphs, λ_{2} of Cayley hypergraphs are far from optimal:

Theorem 1.6 If |G| = n and |H| = d, then the t-uniform Cayley hypergraph on G and H has λ_{2} ≥ n^{(t−2)/4}\sqrt{d(n − d)/n}.

Friedman has recently (see [Fri89]) constructed Cayley hypergraphs that nearly achieve the above lower bound— let AFFINE(p) be the group of affine transformations on Z/pZ, and H = {r^{2}x±r) : r ∈ (Z/pZ)^{∗}}. Then n = p(p−1) and d = 2(p−1). For the associated hypergraph we have:

Theorem 1.7 ([Fri89]) For the above hypergraph, λ_{2} = 2p^{(t−1)/2}.

In sections 2 and 3 we discuss an application of the notion of eigenvalue of a hypergraph, based on a hope of finding explicit constructions to achieve the bounds in theorem 1.4. In section 4 we continue the technical discussion, giving some simple properties of hypergraphs. In section 5 we discribe the “Cayley hypergraphs,” and give some bounds and mention one construction. In section 6 we prove theorem 1.4 and its generalization, theorem 1.5.

2 Dispersers and Randomness

Let Σ = {0, 1}. For a language L ∈ Σ^{∗}, let L_{n} = L∩Σ^{n}. For a function α: N → [0, 1], we define the class RAT E(α) by L ∈ RAT E(α) iff for all (large) n,

\frac{log |L_{n}|}{n} ≤ α(n).

Let k, m: N → N be functions, with k(n), m(n) = n^{O(1)}. We shall be interested in mappings μ : Σ^{∗} → (Σ^{∗})^{k} that for each n, μ : Σ^{m(n)} → (Σ^{n})^{k}. For a language L and a mapping μ, let

μ^{−1}(L) = {y : μ(y)_{i} ∈ L for all 1 ≤ i ≤ k}.

We say that μ is efficient if μ can be computed in determinsitic poly-time.

We say that μ is a (universal) (α, β) rate disperser if ∀L ∈ RAT E(α), μ^{−1}(L) ∈ RAT E(β). (Note that a diperser acts as the “inverse” of compression, i.e. strives to make languages sparser.)

There are several ways in which dispersers are intimately realted to randomized computing, and they all stem from a fundemantal observation of Sipser [Sip86]. Think of L as the language of non-witnesses of some RP algorithm^{1}. Then an efficient disperser μ defines a new RP algorithm, with a language of non-witnesses μ^{−1}(L), which is much sparser.

Typically, L ∈ RAT E(1 − 1/n) (i.e. error probability bounded by 1/2). Sipser [Sip86] and Santha [San86] also gave a probabilistic argument showing that most mappings μ are excellent dispersers.

Theorem 2.1 ([Sip86,San86]) ∀ϵ > 0 there exist (1 − 1/n, n^{ϵ−1}) dispersers.

With our restriction that m(n), k(n) = n^{O(1)}, [CW89] observed that the above theorem is the best possible.

Theorem 2.2 ([CW89]) There are no (1 − 1/n, n^{o(1)−1}) dispersers.

The three motivations for constructing efficient dispersers, and the state of art regarding them are summarized below (see also [CW89]).

1It is natural, and discussed at length in [CW89,IZ89] to consider dispersers for BPP. We do not pursue it here

2.1 Determinsitic Amplification

The first explicit construction of a disperser is implicit in [AKS87].

Theorem 2.3 ([AKS87]) For every k = k(n), there is an efficient (1 − 1/n, 1 − k/m) disperser, with m(n) = n + O(k(n)). (In particular, for some ϵ > 0, efficient (1 − 1/n, 1 − ϵ) dispersers exist.)

By the discussion above, this immediately implies:

Corollary 2.4 ([CW89]) The error probability of any RP algorithm can be d ecreased from 1/2 to 2^{−k} at the cost of only O(k) additional random bits.

The disperser construction of [AKS87] is based on random walks on expander graphs. More elementary, though weaker, dispersers were later constructed in [IZ89].

2.2 Randomness vs. Determinism or Time vs. Space

That efficient dispersers can relate these two fundamental questions of computer science, is the main issue of Sipser’s paper [Sip86].

Theorem 2.5 ([Sip86]) Assume that for some ϵ > 0, efficient (1 − 1/n, n^{−ϵ}) dispersers exist. Then at least one of the following statements hold:

1. RP = P.

2. For some ϵ′ > 0, every t(n) > 2^{n} and infinitely many n, DT IME(t) ⊆ DSP ACE(t^{1−ϵ′}).

As will become clear later, we are far from constructing such good dispersers as this theorem requires, and indeed we offer a way to go about it. However, [NW88] proved by a different mehod that a similar consequence can be proven without any assumptions if we relax (1).

Theorem 2.6 ([NW88]) One of the following statements hold

1. RP = ⋂_{ϵ} DT IME(2^{n^{ϵ}}).

2. For some ϵ′ > 0, t(n) > 2^{n} and infinitely many n, DT IME(t) ⊆ DSP ACE(t^{1−ϵ′}).

2.3 Weak Random Sources

An ensemble Π is a family of probability distibutions Π = (Π_{1}, Π_{2},…) with Π_{n} a distribution of Σ_{n}. A source S is a family of ensembles Π.

A probabilistic algorithm works with source S if on input x it computes a length l = l(x), receives (w.l.o.g) a single^{2} random string σ ∈ Π_{l} from some ensemble Π ∈ S, and from that point proceeds deterministically. The class RP (S) is the class of languages that are recognised by probabilistic poly-time algorithms working with S. Thus, if UNIFORM is the source comprised of the single ensemble U = (U_{1}, U_{2},…), with U_{n} being the uniform distribution on Σ^{n}, then RP = RP(UNIFORM).

Much literature in recent years, e.g.[Blu84,SV84,VV85,CG85,CW89] is devoted to proving RP = RP(S) for a variety of sources S, mostly sources with bounded entropy rate plus structural restrictions.

Say that an ensemble Π is α–FAIR^{3} if for every n, every string σ ∈ Σ^{n} has probability ≤ 2^{−αn}. S is α–FAIR if every Π ∈ S is α–FAIR, and S is FAIR if it is α–FAIR for some α > 0. FAIR sources include most of the sources studied in the literature, and many more.

Theorem 2.7 If efficient (1 − 1/n, α) dispersers exist, then RP = RP (α–FAIR). If for every α > 0 efficient (1 − 1/n, α) dispersers exist, then RP = RP (FAIR).

Cohen and Wigderson [CW89] improved the [AKS87] construction of dispersers, using explicit dense Ramanujan graphs ([Chu88,Hal86]). The following is the best known bound.

Theorem 2.8 ([CW89]) There are efficeint (1 − 1/n, 1/2 + ϵ) dispersers f or every ϵ > 0.

The reason for the 1/2 barrier in the above theorem, and the ideas for breaking it are discussed in the next section.

3 Dispersers, Expanding Hypergraphs and Eigenvalues

Let us consider a mapping μ : Σ^{m} → (Σ^{n})^{k}. We will fix n, though we continue to use asymptotic notation, and the reader should remember we are really working with an infinite family of objects indexed by n.

2In some of the literature on weak random sources multiple access to the source is allowed. However, single access serves to better clarify the probabilistic properties of the source.

3This seems the same as the PRB source of [CG85], only that they allow multiple access to the source (see previous footnote).

μ can be thought of (as in [CW89]) as a bipartite multigraph on Σ^{n} ∪ Σ^{m} with degree k for every vertex in Σ^{m}. Equivallently, it will be considered here as a kuniform (ordered) hypergraph G = G_{μ} = (V, E), with V = Σ^{n} and E ⊆ V^{k}, |E| = 2^{m}.

Let T ⊆ V. Define E(T) = E ∩ T^{k}, i.e. all hyperedges contained in T. It is now natural to call G an (α, β) disperser if for every T ⊆ V with log |T | ≤ α log |V | we have log |E(T)| ≤ β log |E|. In words, if sparse subsets of V contain a sparser set of edges, G is a good disperser. For graphs, (k=2), this is the defining property of expansion, which is why dispersers can be thought of as expanding hypergraphs. Our aim is thus the explicit construction of expanding hypergraphs, where explicit means that the 1-1 mapping μ : Σ^{m} → E is efficiently computable (in P).

Let N = |V | + 2^{n}, |E| = M = 2^{m}. For the hypergraph G and any α = α(n), let

β_{G}(α) = max \begin{cases}log & |E(T)| \\ log & |N| \end{cases} : \frac{log |T |}{log N} ≤ α\}.

By definition, G is a (α, β_{G}(α)) disperser for every α. The question is when do we have β_{G}(α) < α? We shall mainly deal with fixed α ∈ [0, 1], and ignore o(1) terms (i.e. α ≈ α + o(1)).

A natural idea is to compose hypergraphs. If G = (V, E) is k-uniform and H = (E, F) is l-uniform, then the kl-uniform hypergraph G ∘ H = (V, R) is defined by (v_{11},…, v_{1k},…, v_{l1},…, v_{lk}) ∈ R iff (e_{1}, e_{2},…, e_{l}) ∈ F and for every 1 ≤ i ≤ l, e_{i} = (v_{i1},…, v_{ik}) ∈ E.

Composition is clearly useful: if G is an (α, β) disperser and H is a (β, γ) disperser, then G ∘ H is an (α, γ) disperser. Also, if G^{(t)} is the t-fold composition of G with itself, then G^{(t)} is an (α, β_{G}^{(t)}(α)) disperser for every α and t.

Remark: One must remember that we restrict k(n) to be n^{O(1)}, which limits the number of compositions allowed. However, a fixed number of compositions is always allowed.

To understand the tools for constructing dispersers and their limitations, consider simple graphs, i.e. k = 2. Assume G = (V, E) is d-regular, and λ_{1}, λ_{2} the first and second (in absolute value) eigenvalues of its adjacency matrix. Then λ_{1} = d and λ_{2} give a basic upper bound on |E(T)| for every T ⊆ V:

Theorem 3.1 (Easy) |E(T)| ≤ \frac{d}{n}|T |^{2} + λ_{2}|T |.

It is convenient to consider all quantities in logarithms to the base N, so let T = N^{α}, d = N^{δ}, λ_{2} = N^{γ}. The theorem above gives a function β̄_{G} ≥ β_{G}, with

β̄_{G}(α) = \{ \begin{matrix}\frac{2α+δ−1}{1+δ} & if α ≥ 1 + γ − δ \\ \frac{γ+α}{1+δ} & if α ≤ 1 + γ − δ \end{matrix}

Note that β̄(α) ≤ α only if α ∈ [γ/δ, 1 + γ − δ]. The proof of thm [CW89] is essentially an application of this fact, together with the composition of (explicitely constructable) graphs with γ/δ = 1/2 for dense enough sequences of value δ.

This method gets stuck at 1/2, as no explicit construction with γ/δ < 1/2 (i.e. λ_{2} − d^{1/2−ϵ}) is known (for interesting d). In fact, if d ≤ N/2, this is impossible.

Theorem 3.2 (Easy) λ_{2} ≥ \sqrt{d(n − d)/n}.

To see how bad this eigenvalue estimate β̄ is relative to β, even for random graphs, consider as an example a random graph G of degree d = \sqrt{N}, and sets T, |T | = \sqrt{N}. With high probability, λ_{2} = O(N^{1/4}) = O(d^{1/2}), so β̄_{G}(1/2) = 1/2. However, with high probability, |E(T)| = O(\sqrt{N}), so

\begin{matrix}log & |E(T)| \\ log & |E| \end{matrix} = \frac{1}{3},

and β_{G}(1/2) = 1/3. This means that most graphs G with degree \sqrt{N} are (1/2, 1/3) dispersers, but the eigenvalue bound does not prove it.

This is bad news, since for explicitely constructed graphs, the eigenvalues of the associated matrices are almost the only means to bound |E(T)|.

To give a better bound for |E(T)|, we observe that for a k-uniform hypergraph G = (V, E) on n vertices, with second eigenvalue with respect to d-regularity λ_{2}, the following generalization of proposition 3.1 holds.

Theorem 3.3 For every T ⊆ V, |E(T)| ≤ \frac{d}{n}|T |^{k} + λ_{2}|T |^{k/2}.

For every d-regular k-uniform hypergraph, λ_{1}(G) = dn^{(k−2)/2}, and for every kuniform hypergraph on dn^{k−1} edges certainly λ_{1}(G) ≥ dn^{(k−2)/2}. It is therefore surprising and promising that according to theorem 1.4 there exist k-uniform hypergraphs with dn^{(k−2)/2} edges whose second eigenvalue is ≤ (c log n)^{k/2}\sqrt{d}.

Call a d-regular hypergraph G with λ_{2}(G) = O(\sqrt{d}) Ramanujan. It turns out that for our purposes, even explicitely constructible hypergraphs G with λ_{2}(G) = 2^{O(k)}N^{o(1)}d^{O(1)} will suffice to construct better dispersers than the state of the art. We cannot build such expanding hypergraphs. In section 5 we describe methods for explicitly construcing hypergraphs with nontrivial bounds on λ_{2}, and hope these will be improved upon.

Let us consider again the eigenvalue estimate β̄_{G}, for highly expanding hypergraphs. Recall that T = N^{α}, d = N^{δ}, λ_{2} = N^{γ}. Then for α ≤ \frac{2}{k}(1 + γ − δ),

β̄_{G}(α) = \frac{γ + \frac{αk}{2}}{δ + k − 1}. So β̄_{G} is decreasing in the interval [\frac{2γ}{k + 2δ − 2}, \frac{2}{k}(1 + γ − δ)], with a unique fixed point in the left boundary. Composing G with itself can get us

arbitrarily close to the left boundary, i.e. β̄_{G}(t) (\frac{2}{k}(1 + γ − δ)) ⟼_{t→∞} \frac{2γ}{k + 2δ − 2}. This motivates two definitions:

Definition 3.4 (k, δ, γ) will denote that there is an explicitely constructed family of k-uniform hypergraphs G_{i}(V_{i}, E_{i}) (of dense enough cardinalities) with d_{i} = |V_{i}|^{δ} and λ_{2}(G_{i}) = O((V_{i})^{γ}).

For example, the graphs of projective geometries and the graphs of Chung respectively give:

Theorem 3.5 (Hall) For every integer r ≥ 2, (2, 1 − 1/r, 1/2(1 − 1/r)).

Theorem 3.6 (Chung, Katz) For every integer r ≥ 2, (2, 1/r, 1/2r).

Definition 3.7 [α ↦ β] will denote that for every ϵ > 0 there is an explicit dense enough family of (α + ϵ, β + ϵ)-dispersers.

A useful observation is:

Lemma 3.8 [α ↦ β], [β ↦ γ] ⇒ [α ↦ γ]

The discussion above implies in this notation:

Theorem 3.9

(k, δ, γ) ⇒ [\frac{2}{k}(1 + γ − δ) ↦ \frac{2γ}{k + 2δ − 2}]

This and either of the theorems above ([Hall, Chung]) imply:

Theorem 3.10 (1 − τ ↦ 1/2) for every fixed τ > 0.

Using this theorem, Theorem [CW89] is implied from [AKS87].

For Ramanujan hypergraphs, γ = δ/2. To realize their potential we prove:

Theorem 3.11 [For every fixed k, (k, 1/2, 1/4)] ⇒ [1/2 ↦ 0] ⇒ RP = RP (F AIR).

We picked δ = 1/2 and γ = 1/4 as an example. The interested reader can compute the envelope of values for which the consequence RP = RP (F AIR) holds.

Proof: The premise (k, 1/2, 1/4) implies, by Theorem 3.9 that

[\frac{3}{2k} ↦ \frac{1}{2(k − 1)}]

for every k. Using Lemma 3.8 and composition, we get [3/4 ↦ 0]. With [CW89] and Theorem 2.7 this implies RP = RP (F AIR).

4 Basic Facts about Hypergraphs

In this section we will prove some basic facts about the eigenvalues of hypergraphs. We will call a multilinear form, τ, d-regular if it satisfies the conditions of regularity stated before for hypergraphs.

Theorem 4.1 Let τ be a non-negative, d-regular k-linear form on n vertices. Then the first eigenvalue of H is dn^{(k−2)/2}, with 1 ⊗ ⋯ ⊗ 1 being an eigenvector.

Proof We shall proceed by induction on k. For k = 1 this is clear, for then the associated multilinear form, τ, is just a one-dimensional vector proportional to 1. For general k, let the associated trilinear form, τ, take its maximum over the product of unit balls at (u_{1},…, u_{k}). Since τ has non-negative coefficients, we can assume that each u_{i} has non-negative coefficients (or replace the u_{i} by such vectors while preserving their norm and without decreasing the absolute value of τ at (u_{1} …, u_{k})). But viewing u_{1} as fixed, the k−1 form τ(u_{1}, ·,…, ·) is easily seen to be a non-negative, θ-regular form where θ is the sum of the components of u_{1}; therefore, by induction, then norm of this k − 1-linear form is θn^{(k−3)/2}, with 1 ⊗ ⋯ ⊗1 being a coresponding eigenvector. But the ratio of θ to ∥u_{1}∥ is maximized when u_{1} is proportional to 1, and so the norm of τ is dn^{(k−2)/2}, with 1 ⊗ ⋯ ⊗1 being a corresponding eigenvector.

□

Theorem 4.2 Let τ be a symmetric k-linear form. Then there is a vector u ∈ L^{2}(V) such that u ⊗ ⋯ ⊗ u is a first eigenvector for τ.

Lemma 4.3 Let ν be a symmetric 2-linear form. If u and v are unit vectors such that ∥ν∥ = |ν(u, v)|, then also ∥ν∥ = |ν(u, u)|.

Proof By linear algebra, ν is diagonalizable with an orthonormal basis. Let ν̃ be the associated endomorphisn of L^{2}(V). If ν̃’s largest eigenvalue in absolute value is λ, then ∥ν∥ = |λ| = ∥ν̃∥. Since

|λ| = |ν(u, v)| = |(ν̃(u), v)| ≤ ∥ν̃(u)∥∥v∥ = ∥ν̃(u)∥,

u must be an eigenvector with corresponding eigenvalue = ±∥ν∥, and so ∥ν∥ = |ν(u, u)|.

□

The theorem easily follows. If u_{1} ⊗ ⋯ ⊗ u_{k} is a first eigenvector for τ, then applying the lemma to the bilinear form τ(·, ·, u_{3},…, u_{k}) we see that we can replace u_{2} by u_{1}. Similarly we can replace all the u_{i} by u_{1}, successively, proving the theorem.

□

We now give a lower bound for the second eigenvalue. Since the projection of a vector with a ones and n − a zeros onto 1^{⊥} has norm \sqrt{a(n − a)/n}, the following proposition follows immediately from the definition of second eigenvalue:

Proposition 4.4 Let H be a k-uniform, d-regular hypergraph. For any subsets U_{1},… U_{k} of V, the number of edges in U_{1} × ⋯ × U_{k} is

\frac{d}{n}|U_{1}| ⋯ |U_{k}| + θλ_{2}\sqrt{\frac{|U_{1}|(n − |U_{1}|)}{n}} ⋯ \sqrt{\frac{|U_{k}|(n − |U_{k}|)}{n}}

for some θ with |θ| ≤ 1, and where λ_{2} is the second eigenvalue of the hypergraph.

Now take any U_{1},…, U_{k−1} consisting of one vertex. Then we can find a U_{k} of size n − d for which E contains no edges in U_{1} × ⋯ × U_{k}. It follows that:

Proposition 4.5 Let H be as in proposition 4.4. Then

λ_{2} ≥ \sqrt{\frac{d(n − d)}{n}}.

In the literature there are many methods for obtaining upper and lower bounds on the second eigenvalue of graphs. We remark that when we consider the bilinear form τ(v_{1},…, v_{k−2}, ·, ·) with each v_{i} being one of the standard vectors, e_{j}, we get a dregular graph, and can therefore apply lower bounds known for the second eigenvalue of graphs. The preceding proposition is an example. Applying another known lower bound for graphs (see [Alo86]) yields:

Proposition 4.6 For some constant C we have that if d ≤ n^{1/C} then λ_{2} ≥ 2\sqrt{d − 1}− C/ log_{d} n.

As for obtaining upper bounds, the strongest methods don’t seem to directly generalize. The so-called “trace method,” which uses multiplication of graphs and taking the trace of a graph (its adjacency matrix), does not have an obvious generalization (that we see). However, for graphs which are Cayley graphs, such as those of [LPS86] and [Mar87], there is a natural generalization, and it turn out that to analyze their second eigenvalue is suffices to analyze the second eigenvalue of the corresponding graph (and to understand the representations of the underlying group), so the trace method can be applied there. For random graphs, we don’t know how to apply results that use the trace method, such as those of [Wig55], [BS87], [Fri88]. However the method of Kahn and Szemerédi, in [FKS89], does generalize quite readily, and we can prove theorem 1.4, which will be done in section 6.

For applications we would like to come up with constructions to match this bound. Often we would like the graph to be constructible in poly log of the number of nodes, for example in using weak random sources. We do not have an explicit construction to match the bound in theorem 1.4, not even one which is constructable in polynomial time in the number of nodes. We will describe two types of constructions; one is very easy, and yields a weak eigenvalue bound. The second type is an analogue of Cayley graphs, which we call Cayley hypergraphs. This gives somewhat improved bounds, but we also give a lower bound to show that Cayley hypergraphs cannot match the bound of theorem 1.4. We find this interesting because most explicit constructions of graphs with small second eigenvalue that we know are Cayley graphs. Perhaps there is a better generalization of this concept that can yield hypergraphs with small second eigenvalue; one such construction might be buildings with finite groups or finite quotients of buildings of rank t − 1 Lie groups (for t-uniform hypregraphs) (see [BT71]). We finish this section by giving an easy construction for a graph with slightly small second eigenvalue.

Let G = (V, E) be any graph which is d-regular, and let G̃ = (V, V^{t−2} × E).

Proposition 4.7 If λ_{2} is the second eigenvalue of G, then the second eigenvalue of Ĝ is no greater than \sqrt{n}|λ_{2}|.

Proof It is easy to see that the associated τ is d-regular. If v, w ∈ {1}^{⊥}, then clearly |τ(e_{i}, v, w)| ≤ λ_{2}∥v∥∥w∥ for any standard basis vector e_{i}. Thus

|τ(u, v, w)| ≤ (∑_{i=1}^{n} |u_{i}|) λ_{2}∥v∥∥w∥ ≤ \sqrt{n}λ_{2}∥u∥∥v∥∥w∥.

5 Cayley Hypergraphs

Let G be a group, and H a subset of G. The Cayley graph on G generated by H is defined to be the graph with vertex set G and edge set

{(x, y) | xy^{−1} ∈ H}.

(We do not require that H generate G, nor that H = H^{−1}.) This gives a d-regular directed graph, and if H = H^{−1} we can view the graph as undirected. We define the Cayley sum graph similarly, though taking the edge set to be

{(x, y) | xy ∈ H}.

Perhaps the easiest way to get a 3-regular hypergraph from this data is to keep G as the set of vertices and to take

{(x, y, z) | xyz ∈ H}

as the edge set; we will call this hypergraph the (3-regular) Cayley hypergraph on G and H.

The eigenvalues of Cayley graphs and, as we shall see, hypergraphs, can often be estimated when one understands the decomposition of L^{2}(G) under the right regular representation. We recall the following facts about representations of finite groups (see [Rob83] for details). We will, for the moment, let L^{2}(G) denote the space of complex-valued functions on G with the usual inner product:

(u, v) = ∑_{g∈G} u_{g}\overline{v_{g}}.

L^{2}(G) can be decomposed into subspaces

L_{2}(G) = ⨁_{i=1}^{r} E_{i}

with the following conditions:

1. Each E_{i} is invariant under the natural action of G on L_{2}(G), given by g(u(x)) ≡ u(gx).

2. dim(E_{i}) = d_{i}^{2} for some d_{i} corresponding to the dimension of an irreducible unitary representation of G, ρ_{i} : G → Gl(C, d_{i}), in the sense that a complete orthogonal basis for E_{i} is given by the d_{i}^{2} entries of ρ_{i} with respect to any basis of C^{n}. Also, the norm of each coefficient of ρ_{i}, as an element of L^{2}(G), has norm \sqrt{n/d_{i}}.

3. r is equal to the number of conjugacy classes in G.

It follows that the matrix A of any Cayley graph on G vanishes outside the E_{i} × E_{i} blocks, in the sense that τ(u, v) = 0 if u and v are contained in different E_{i}’s. More generally, the t-regular hypergraph generated by G and H vanishes outside the E_{i} ×⋯×E_{i} blocks. Let us assume, for simplicity, that the Cayley graph is generated by an H which satisfies H=H^{−1}. It then follows that the eigenvalues of A are real, and there is an orthogonal set of real eigenvectors.

Theorem 5.1 Let the eigenvalues of A restricted to E_{i} be λ_{1},… λ_{d_{i}^{2}}. Then the norm of the t-linear form associated to the t-regular Cayley hypergraph on G and H is

(\frac{n}{d_{i}} )^{(t−2)/2} max_{j} |λ_{j}|.

Corollary 5.2 The second eigenvalue of a t-uniform Cayley hypergraph of degree d is at least \sqrt{d(n − d)/n} n^{(t−2)/2}.

Proof For simplicity we will first prove this for 3-regular hypergraphs, and then indicate how to generalize the proof. Let A and τ, by abuse of notation, denote the adjacency matrix and bilinear form, respectively, associated to the Cayley graph restricted to the subspace E, corresponding to the d dimensional representation ρ. For any basis of C^{d}, we can consider the coefficients of ρ, {ρ_{i,j}}, with respect to a given basis for E, w_{1},…, w_{d}. For any i, j, k, l, we have

∑_{xy=h} ρ_{i,j}(x)ρ_{k,l}(y) = ∑_{g∈G} ρ_{i,j}(g)ρ_{k,l}(g^{−1}h)

which, using the fact that ρ is a unitary representation, is

∑ g ∈ G ∑_{m=1}^{d} ρ_{i,j}(g)\overline{ρ_{l,m}(g)}ρ_{m,k}(h) = δ_{i,k} (\frac{n}{d}) ρ_{j,l}(h),

where δ_{i,k} is the Kronecker delta function. It follows that τ is given by

τ (∑_{i,j} α_{i,j}ρ_{i,j}, ∑_{k,l} β_{k,l}ρ_{k,l}) = ∑_{i,j,k,l} α_{i,j}β_{k,l}δ_{i,k}M_{j,l} = ∑_{i,j,l} α_{i,j}β_{i,l}M_{j,l}

where M_{j,l} is given by the matrix equation

M = (\frac{n}{d}) ∑_{h∈H} ρ(h).

Since H = H^{−1}, it follows that M is a real symmetric matrix, and therefore is diagonalizable by a set of real eigenvectors in R^{d} with real eigenvalues. Take these eigenvectors as the basis of C^{d}, w_{1},…, w_{d}. Then M becomes a diagonal matrix. Since the norm of each ρ_{i,j} is \sqrt{n/d}, it follows that for each i, j, the function ρ_{i,j} is an eigenvector of the adjacency matrix, with eigenvalue 0 if i ≠ j, and eigenvalue λ_{i,i} = \frac{d}{n}M_{i,i} if i = j.

Now let ν be the trilinear form associated to the 3-regular hypergraph generated by G and H. A similar calculation shows that ν is given by

ν (∑_{i,j} α_{i,j}ρ_{i,j}, ∑_{k,l} β_{k,l}ρ_{k,l}, ∑_{q,r} γ_{q,r}ρ_{q,r}) = ∑ α_{i,j}β_{k,l}γ_{q,r}δ_{i,k}δ_{j,q}δ_{l,r} \frac{n}{d}M_{l,l}

= ∑ α_{i,j}β_{i,l}γ_{j,l} \frac{n}{d}M_{l,l}

It follows that ν(ρ_{i,i}, ρ_{i,i}, ρ_{i,i}) is \frac{n}{d}M_{i,i}, and so

∥ν∥ ≥ \sqrt{\frac{n}{d}}λ_{i,i}

for each i. We claim this hitting the ν with ρ_{i,i} is the best that we can do, i.e.

Proposition 5.3 We have

∥ν∥ = max_{i} \sqrt{\frac{n}{d}}|λ_{i,i}|.

Proof Let α_{i,j}, β_{k,l}, γ_{q,r} be given with

∑_{i,j} α_{i,j}^{2} = ∑_{i,j} β_{i,j}^{2} = ∑_{i,j} γ_{i,j}^{2} = 1.

It suffices to obtain the estimate

∑_{i,j,k} α_{i,j}β_{i,k}γ_{j,k} ≤ 1.

Letting

a_{j,k} = ∑_{i} α_{i,j}β_{i,k},

we see that applying Cauchy-Schwartz inequality yields

∑_{j,k} a_{j,k}^{2} ≤ ∑_{j,k} (∑_{i} α_{i,j}^{2}) (∑_{i} β_{i,k}^{2}) = 1

and so

∑_{j,k} a_{j,k}γ_{j,k} ≤ (∑_{j,k} a_{j,k}^{2})^{1/2} (∑_{j,k} γ_{j,k}^{2})^{1/2} ≤ 1.

□

The generalization of theorem 5.1 to t-uniform hypergraphs follows from similar considerations, and the generalized estimate:

Proposition 5.4 Let α_{i,j}^{1}, α_{i,j}^{2}, ⋯, α_{i,j}^{s} be s n×n arrays of numbers with ∑_{i,j}(α_{i,j}^{r})^{2} = 1 for each r. Then

∑ α_{i_{1},i_{2}}^{1}α_{i_{1},i_{3}}^{2}α_{i_{2},i_{4}}^{3}α_{i_{3},i_{5}}^{4} ⋯ α_{i_{k−2},i_{k}}^{k−1}α_{i_{k−1},i_{k}}^{k} ≤ 1

Proof Let

a_{j,k}^{r} = ∑ α_{i_{1},i_{2}}^{1}α_{i_{1},i_{3}}^{2}α_{i_{2},i_{4}}^{3}α_{i_{3},i_{5}}^{4} ⋯ α_{i_{r−2},j}^{r−1}α_{i_{r−1},k}^{r}

for r < k. By induction on r, using Cauchy-Schwartz as before, one can prove that

∑_{j,k}(a_{j,k}^{r})^{2} ≤ 1

for all r, and therefore prove the proposition, by estimating

∑_{j,k} a_{j,k}^{k−1}α_{j,k}^{k} ≤ (∑_{j,k}(a_{j,k}^{k−1})^{2})^{1/2} (∑_{j,k}(α_{j,k}^{k})^{2})^{1/2} ≤ 1.

6 Random Hypergraphs

First we will prove theorem 1.4, and then theorem 1.5 for arbitrary t. In this section, C, C′, C_{1}, etc. will each denote various absolute positive constants unless otherwise indicated. Throughtout this section the phrase “with high probability” is short for there exist constants C, C′ such that the event occurs with probability at least 1 − Cn^{−C′ min(\sqrt{d},n^{1/(t+3)})/t}. When we prove theorem 1.4, we take t = 3 in this formula, but for for theorem 1.5 this is to hold for all t with C and C′ are independent of t.

Proof of theorem 1.4 To avoid issues of the model we work with the probability space G_{n,d} of random 3-uniform hypergraphs on n vertices which has dn^{2} directed edges chosen at random independently and uniformly from all possible n^{3} “edge slots.” A graph in G_{n,d} won’t in general be d-regular, but we will estimate its second eigenvalue with respect to d-regularity. G_{n,d} graphs are approximately d-regular in the following two senses:

Lemma 6.1 Let d ≥ ρ log n with ρ ≥ C_{0}. With probability 1 − n^{C_{1}ρ}, a τ ∈ G_{n,d} will satisfy

∑_{i∈A,j∈B,1≤k≤n} τ_{ijk} ≤ C_{2}d|A||B|

for every A, B ⊂ V, and the same with τ_{ijk} replaced by τ_{ikj} or τ_{kij}.

Proof The probability that τ does not satisfy the equation is bounded by

∑_{a,b=1}^{n} \binom{n}{a}\binom{n}{b}B(dn^{2}, Cdab, ab/n^{2}),

where B(r, s, t) denotes the probability of at least s successes in r Bernoulli trials of probability t. Since B(r, s, t) ≤ r\binom{r}{s}t^{s} ≤ (ert/s)^{s}r, we have

B(dn^{2}, Cdab, ab/n^{2}) ≤ (e/C)^{Cdab}dn^{2},

and the right-hand-side of the above is clearly bounded by n^{−C_{1}ρ} for some positive C_{1}.

Lemma 6.2 With probability 1 − Cn^{−C′n^{1/5}}, a τ in G_{n,d} will have

|τ(1/\sqrt{n}, u, v)| ≤ C(log n)\sqrt{d}∥u∥∥v∥

for all u, v ∈ \{1\}^{⊥}, and similarly with the 1/\sqrt{n}, u, v permuted in any order. The same holds with u replaced by 1/\sqrt{n}.

Proof The matrix, A, given by

A_{ij} = ∑_{k=1}^{n} τ_{kij}

is a random graph on n vertices with average degree nd. It would be a standard fact that with very large probability

∥A − d1 ⊗ 1∥_{2} ≤ C\sqrt{nd}

for a slightly different model of random A, e.g. if A’s entries were chosen independently from some distribution. This is not the case here, but since we are willing to settle for a ≤ C\sqrt{d} log n estimate, it is easiest to note that this follows from the generalization of theorem 6.3, theorem 6.7, for 2-uniform hypergraphs with d replaced by dn. (The proof of theorem 6.3 and its generalization does not use lemma 6.2.) This proves the first part of lemma 6.2. The second part of the lemma is just a direct calculation— it suffices to show that dn^{2} Bernoulli trials with success probability 1/n have dn ± O(\sqrt{d}n) successes with large probability. This indeed occurs with probability ≥ 1 − C^{n} with some C < 1.

To prove theorem 1.4, we estimate λ_{2,d}(τ) by writing

τ(u_{1},…, u_{3}) = τ(ũ_{1} + α_{1}1,…, ũ_{3} + α_{3}1)

with ũ_{i} ∈ {1}^{⊥} and α_{i} ∈ R, and use multilinearity. By lemma 6.2, we see that theorem 1.4 follows from:

Theorem 6.3 With probability 1 − n^{−C′ min(\sqrt{d},n^{1/6})}, a τ in G_{n,d} satisfies

|τ(u, v, w)| ≤ C\sqrt{d}(log n)^{3/2}∥u∥∥v∥∥w∥  (6.1)

for all u, v, w ∈ {1}^{⊥}.

Proof For the proof we use the Kahn-Szemerédi approach of estimating the second eigenvalue of a random graph, see [FKS89]. Clearly it suffices to prove this for all u, v, w in some large finite set, M ⊂ {1}^{⊥}; in fact one can take

M = (\frac{1}{4\sqrt{n}}Z)^{n} ∩ \{1\}^{⊥} ∩ B_{1}(0),

where B_{1}(0) denotes the unit ball, for it is easy to see that any u ∈ {1}^{⊥} ∩ B_{1}(0) can be written as

u = ∑_{i=−1}^{∞} (\frac{1}{4})^{i} u_{i}

with u_{i} ∈ M, and thus

|τ(u, v, w)| ≤ |τ (∑ (\frac{1}{4})^{i} u_{i}, ∑ (\frac{1}{4})^{i} v_{i}, ∑ (\frac{1}{4})^{i} w_{i})| ≤ C\sqrt{d}(log n)^{3/2} ( ∑_{i=−1} (\frac{1}{4})^{i})^{3}

if u_{i}, v_{i}, w_{i} ∈ M, assuming that equation 6.1 holds for all u, v, w ∈ M. It is easy to check, see [FKS89], that |M| ≤ C^{n}.

Fix u, v, w ∈ M, and write u = ∑ u_{i}e_{i}, and similarly for v and w, where e_{i} are the standard basis. We break the sum

τ(u, v, w) = ∑ u_{i}v_{j}w_{k}τ_{ijk}

into two sums, by setting

S = \{(i, j, k) | |u_{i}v_{j}w_{k}| ≤ \sqrt{d}/n\}.

S represents the “small tuples” u_{i}v_{j}w_{k}. We now argue first that: Lemma 6.4 For any C there is a C′ such that for a given u, v, w,

| ∑_{(i,j,k)∈S} u_{i}v_{j}w_{k}τ_{ijk}| ≤ C′\sqrt{d}

for τ ∈ G_{n,d} with probability ≥ 1 − C^{−n}. Since there are |M|^{3} = C^{3n} such tuples, lemma 6.4 holds for all (u, v, w) ∈ M^{3} with high probability.

On the other hand we claim that the sum outside S will, for most hypergraphs, be a priori bounded by C\sqrt{d}, a condition that is only violated when certain “unusually high edge densities” occur in τ. Lemma 6.5 With high probability, a τ ∈ G_{n,d} satisfies

|∑_{\overline{S}} u_{i}v_{j}w_{k}τ_{ijk}| ≤ C(log n)^{3/2}\sqrt{d}

for all u, v, w.

It remains to prove the above two lemmas. First notice that

|∑_{S} u_{i}v_{j}w_{k}| = |∑_{\overline{S}} u_{i}v_{j}w_{k}| ≤ \frac{n}{\sqrt{d}},

since

|∑_{\overline{S}} u_{i}v_{j}w_{k}| ≤ \frac{n}{\sqrt{d}} ∑_{\overline{S}} u_{i}^{2}v_{j}^{2}w_{k}^{2} ≤ \frac{n}{\sqrt{d}}.

Lemma 6.4 is now a standard calculation: we have

E \{e^{∑_{S} λu_{i}v_{j}w_{k}τ_{ijk}}\} = (∑_{S} \frac{1}{n^{3}} e^{λu_{i}v_{j}w_{k}})^{dn^{2}}

= (e^{\frac{1}{n^{3}} ∑_{S} λu_{i}v_{j}w_{k}}e^{\frac{1}{n^{3}} ∑_{S} O(λu_{i}v_{j}w_{k})^{2}})^{dn^{2}} = e^{\frac{d}{n} λ ∑_{S} u_{i}v_{j}w_{k}}e^{\frac{d}{n} λ^{2}O(1)} provided that λu_{i}v_{j}w_{k} = O(1) for all (i, j, k) ∈ S, with an absolute constant in the O( ) notation. Taking λ = n/\sqrt{d} yields e^{O(n)} in the above, and thus

Pr \{∑_{S} u_{i}v_{j}w_{k}τ_{ijk} ≥ C\sqrt{d}\} ≤ e^{−Cn}e^{O(n)}.

Taking λ = −n/\sqrt{d} yields a similar exponential lower bound:

Pr \{∑_{S} u_{i}v_{j}w_{k}τ_{ijk} ≤ −C\sqrt{d}\} ≤ e^{−Cn}e^{O(n)}

for a positive constant C.

To prove lemma 6.5, we consider for subsets A, B, C ⊂ V,

e(A, B, C) ≡ ∑_{i∈A,j∈B,k∈C} τ_{ijk}

and

ẽ(A, B, C) ≡ ∑_{i∈A,j∈B,k∈C,(i,j,k)∈\overline{S}} τ_{ijk}.

The standard counting argument and estimates yield:

Lemma 6.6 With probability 1 − ϵ we have that a τ ∈ G_{n,d} satisfies for all subsets A, B, C ⊂ V,

e(A, B, C) ≤ k(|A|, |B|, |C|)

where k = k(a, b, c) is any function of a, b, c satisfying

\binom{n}{a}\binom{n}{b}\binom{n}{c} (\frac{e\frac{d}{n}abc}{k})^{k} ≤ \frac{ϵ}{n^{3}}

for all a, b, c.

Proof A standard calculation, using the estimate \binom{a}{b} ≤ (ea/b)^{b}.

The above lemma gives a condition that the hypergraph have no “irregular (overly large) edge densities.” Now we set for i > 0

A_{i} = {j | 2^{−i} < u_{j} ≤ 2^{−i+1}} ⊂ {1,…, n}

and

A_{−i} = {j | 2^{−i} < −u_{j} ≤ 2^{−i+1}} ⊂ {1,…, n}

and similarly define B_{i} and C_{i}; note that for m = ⌊log(4\sqrt{n})⌋, we have that the above sets are empty when i > m. We now estimate

∑_{u_{i},v_{j},w_{k}>0, \overline{S}} u_{i}v_{j}w_{k}τ_{ijk} ≤ ∑_{α,β,γ=1}^{m} ∑_{\overline{S}∩A_{α}×B_{β}×C_{γ}} ẽ(A_{α}, B_{β}, C_{γ})\overline{u}_{α}\overline{v}_{β}\overline{w}_{γ}  (6.2)

where \overline{u}_{α} = 2^{−α+1} and similarly for \overline{v} and \overline{w}. (Thus \overline{u}_{α} approximates every u_{i} with i ∈ A_{α}; we use this notation to be suggestive.) The game becomes to choose an appropriate k = k(a, b, c) in the above lemma to get good estimates in equation 6.2. Then we do the same for the analogue of equation 6.2 with the sum over all other sign combinations for α, β, gamma, and we are done.

To estimate the right-hand-side of equation 6.2, note that we can assume that |C_{γ}| is at least as large as |A_{α}| and |B_{β}| (and then repeating the argument when |A_{α}| and then |B_{β}| are the largest). We may also assume that

\overline{u}_{α}\overline{v}_{β} ≤ \sqrt{d} \overline{w}_{γ},  (6.3)

for each term, for if not then take out such terms and note that since ∑_{γ} ẽ ≤ ∑_{γ} e ≤ Cd|A_{α}||B_{β}|,

∑ ẽ(A_{α}, B_{β}, C_{γ})\overline{u}_{α}\overline{v}_{β}\overline{w}_{γ} ≤ ∑ C\sqrt{d}|A_{α}||B_{β}|\overline{u}_{α}^{2}\overline{v}_{β}^{2} ≤ C\sqrt{d}.

It is easy to see that for d ≤ n^{1/3} the choice of

k(a, b, c) = \{ \begin{matrix}C\sqrt{d} & if c ≤ C′\sqrt{d} \\ C(log n)^{3/2} \frac{d}{n} abc & if ab ≥ \frac{n}{d}(log n)^{−1/2} \\ (log n)^{1/2}c & if ab ≤ \frac{n}{d}(log n)^{−1/2} and c ≥ C′\sqrt{d} \end{matrix}

when c = max(a, b, c) satisfies lemma 6.6 with ϵ = n^{−C′′\sqrt{d}}, while either of the three bounds for k (and therefore ẽ) above give an estimate for the sum in equation 6.2: first of all, where k = C\sqrt{d} we can estimate the sum in equation 6.2

∑_{α,β,γ=1}^{m} ẽ(A_{α}, B_{β}, C_{γ})\overline{u}_{α}\overline{v}_{β}\overline{w}_{γ} ≤ ∑_{α,β,γ=1}^{m} C\sqrt{d}\overline{u}_{α}\overline{v}_{β}\overline{w}_{γ} ≤ C′\sqrt{d}

since each of \overline{u}, \overline{v}, and \overline{w} are geometrically decreasing sequences (i.e. 1, 1/2, 1/4,…). Second, where k is C(log n)^{3/2}(d/n)abc we can estimate the sum by

∑ C(log n)^{3/2} \frac{d}{n}|A_{α}||B_{β}||C_{γ}|\overline{u}_{α}\overline{v}_{β}\overline{w}_{γ}

≤ ∑ C(log n)^{3/2}\sqrt{d}|A_{α}||B_{β}||C_{γ}|\overline{u}_{α}^{2}\overline{v}_{β}^{2}\overline{w}_{γ}^{2} ≤ C′(log n)^{3/2}\sqrt{d},

the first inequality using that fact that each of the tuples is in \overline{S}. Finally, where k is C(log n)^{1/2}c we can estimate the sum by

≤ ∑_{α,β,γ} C(log n)^{1/2}|C_{γ}|\overline{u}_{α}\overline{v}_{β}\overline{w}_{γ} ≤ ∑_{γ} C(log n)^{1/2}|C_{γ}| ∑_{α,β} \overline{u}_{α}\overline{v}_{β},

where the leftmost sum is over all α and β satisfying equation 6.3. Since the \overline{u}’s and \overline{v}’s are a geometric sequence, and since the α and β range over m = O(log n) values, we have that for any fixed γ,

∑_{\overline{u}_{α}\overline{v}_{β}≤\sqrt{d}\overline{w}_{γ}} \overline{u}_{α}\overline{v}_{β} ≤

\sqrt{d}\overline{w}_{γ} (m + \frac{1}{2}m + \frac{1}{4}m + ⋯) ≤ \sqrt{d}\overline{w}_{γ}C′ log n.

Hence the sum in equation 6.2 can be bounded by

∑_{γ} C(log n)^{3/2}\sqrt{d}|C_{γ}|\overline{w}_{γ}^{2} ≤ C(log n)^{3/2}\sqrt{d}.

To finish the proof of theorem 1.4, we must alter slightly our choice of k for d ≥ n^{1/3}. For this case we can chose k as before except replacing each \sqrt{d} by a n^{1/6}, giving us an ϵ of n^{−C′′n^{1/6}}. This completes the proof of theorem 1.4.

□

Proof of theorem 1.5 We indicate what needs to be changed in the previous proof. To prove theorem 1.5 for t-uniform hypergraphs, we estimate λ_{2,d}(τ) by writing

τ(u_{1},…, u_{t}) = τ(ũ_{1} + α_{1}1,…, ũ_{t} + α_{t}1)

with ũ_{i} ∈ {1}^{⊥} and α_{i} ∈ R, and use multilinearity. As before, it suffices to prove a generalization of theorem 6.3 for a random t-linear form, where we prove the estimate

|τ(u_{1},…, u_{t})| ≤ \sqrt{d}(C log n)^{t/2}∥u_{1}∥ ⋯ ∥u_{t}∥

with high probability. To do so, first, in lemma 6.1 we replace “d ≥ ρ log n” by “d ≥ ρt log n,” and “probability 1 − n^{ρC_{1}}” with “high probability;” the proof is the same. In lemma 6.5 we replace 3/2 by t/2. The proof of the lemma is almost identical, except that we choose k slightly differently, namely

k(a_{1},…, a_{t}) = \{ \begin{matrix}C\sqrt{d} & if a_{t} ≤ C′\sqrt{d} \\ C(log n)^{t/2} \frac{d}{n} a_{1} ⋯ a_{t} & if a_{1} ⋯ a_{t−1} ≥ \frac{n}{d}(log n)^{(2−t)/2} \\ (log n)^{(4−t)/2}a_{t} & if a_{1} ⋯ a_{t−1} ≤ \frac{n}{d}(log n)^{(2−t)/2} and a_{t} ≥ C′\sqrt{d} \end{matrix}

for d ≤ n^{2/(t+3)} (assuming a_{t} = max(a_{1},…, a_{t})), and for larger d we replace the \sqrt{d}’s by n^{1/(t+3)}’s. The only difference in the estimates from this point on is that the old estimate

∑_{\overline{u}_{α}\overline{v}_{β}≤\sqrt{d}\overline{w}_{γ}} \overline{u}_{α}\overline{v}_{β} ≤ \sqrt{d} \overline{w}_{γ}C log n

must be replaced by the analogous sum being estimated by

\sqrt{d} \overline{w}_{γ}C(log n)^{t−2}.

In lemma 6.4 we replace C′\sqrt{d} by C′t\sqrt{d}, and prove the inequality with probability 1 − C^{−nt}. We need this because we are counting over M^{t}, whose size is C^{nt}. Thus we can establish the generalization of theorem 6.3:

Theorem 6.7 With high probability, a τ in G_{n,d,t} satisfies

|τ(u_{1},…, u_{t})| ≤ C\sqrt{d}(log n)^{t/2}∥u_{1}∥ ⋯ ∥u_{t}∥

for all u_{1},…, u_{t} ∈ {1}^{⊥}.

Here G_{n,d,t} is the space of random t-uniform hypergraphs with n vertices and with dn^{t−1} edges chosen at random from all n^{t} possible “edge slots.”

The analog of lemma 1.2 is that with high probability, a τ in G_{n,d,t} satisfies

|τ(u_{1},…, u_{t})| ≤ C\sqrt{d}(log n)^{(t−1)/2}

for all u_{1},…, u_{t} with at least one of the u_{i}’s = 1/\sqrt{n}, and with each other u_{i}’s either = 1/\sqrt{n} or in \{1\}^{⊥}∩B_{1}(0). As before, this follows from theorem 6.7. Since each of the ≤ 2^{t} ways of fixing a subset of u’s to 1/\sqrt{n} satisfies the desired inequality with high probability, all ≤ 2^{t} inequalities are satisfied simultaneously with high probability (note the definition of high probability has a 1/t factor in the exponent). To finish, we use multilinearity, as described in the beginning of the proof of theorem 1.5.

□

We remark that our choice of k is more relaxed that the choice of k in [FKS89], and consequently the analysis is easier at the cost of possibly forsaking a log n factor. If we replaced, say, the first k in the proof of theorem 1.4 by

k(a, b, c) = \{ \begin{matrix}C\sqrt{d} & if c ≤ C′\sqrt{d} \\ C \frac{d}{n} abc & if ab ≥ \frac{n}{d}(log n) \\ r(a, b, c) & if ab ≤ \frac{n}{d}(log n) and c ≥ C′\sqrt{d} \end{matrix}

where r = r(a, b, c) satisfies for some large enough C

r log \frac{r}{abcd/n} = Cc log \frac{n}{c},

one could perhaps perform a more careful analysis to recover a log n factor (see [FKS89]). Perhaps one could also replace the (C log n)^{t/2} entirely by a small constant, but we don’t see how to do this at this point.

References

[AKS87] M. Aitai, J. Komlós, and E. Szemerédi. Deterministic simulation in LOGSPACE. STOC, 1987.

[Alo86] N. Alon. Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986.

[Blu84] M. Blum. Independent unbiased coin flips from a correlated sources: a finite state markov chain. FOCS, pages 425–433, 1984.

[BS87] Andrei Broder and Eli Shamir. On the second eigenvalue of random regular graphs. In 28th Annual Symposium on Foundations of Computer Science, pages 286–294, 1987.

[BT71] F. Bruhat and J. Tits. Publ. Math. IHES, 1971.

[CG85] B. Chor and O. Goldriech. Unbiased bits from sources of weak randomness and probabilistic communication complexity. FOCS, pages 429–442, 1985.

[Chu88] F. R. K. Chung. Diameters and eigenvalues. preprint, 1988.

[CW89] A. Cohen and A. Wigderson. Dispersers, deterministic amplification, and weak random sources. FOCS, 1989.

[FKS89] J. Friedman, J. Kahn, and E. Szemerédi. On the second eigenvalue of random graphs. STOC, 1989.

[Fri88] J. Friedman. On the second eigenvalue of random d-regular graphs. Technical report, Princeton University, August 1988. To appear in Combinatorica.

[Fri89] J. Friedman. Some graphs with small second eigenvalue. Technical report, Princeton University, October 1989.

[Hal86] M. Hall. Combinatorial Theory. John Wiley & Sons, 2nd edition, 1986.

[IZ89] R. Impagliazzo and D. Zuckerman. How to recycle random bits. FOCS, 1989.

[LPS86] A. Lubotzky, R. Phillips, and P. Sarnak. Explicit expanders and the ramanujan conjectures. In 18th Annual ACM Symposium on Theory of Computing, pages 240–246, 1986.

[Mar87] G. Margulis. Manuscript in Russian on graphs with large girth, 1987.

[NW88] N. Nissan and A. Wigderson. Hardness vs. randomness. FOCS, pages 2–11, 1988.

[Rob83] Alain Robert. Introduction to the Representation Theory of Compact and Locally Compact Groups. Cambridge University Press, Cambridge, 1983.

[San86] M. Santha. On using detrnimistic functions to reduce randomness in probabilistic algorithms. 1986. manuscript.

[Sip86] M. Sipser. Expanders randomness or time versus space. Structure and Complexity Theory, 1986.

[SV84] M. Santha and U. V. Vazirani. Generating quasi-random sequences from slightly random sources. FOCS, pages 434–440, 1984.

[VV85] U. V. Vazirani and V. V. Vazirani. Random polynomial time is equal to slightly random polynomial time. FOCS, pages 417–428, 1985.

[Wig55] E. Wigner. Characteristic vectors of bordered matrices with infinite dimensions. Annals of Math., 63(3):548–564, 1955.