The Spectra of Infinite Hypertrees

Joel Friedman^{∗} Department of Computer Science Princeton University Princeton, NJ 08544

September 13, 1990

Abstract

We develop a model of regular, infinite hypertrees, to mimic for hypergraphs what infinite trees do for graphs. We then examine two notions of spectra or “first eigenvalue” for the infinite tree, obtaining a precise value for the first notion and obtaining some estimates for the second. The results indicate agreement of the first eigenvalue of the infinite hypertree with the “second eigenvalue” of a random hypergraph of the same degree, to within logarithmic factors, at least for the first notion of first eigenvalue.

1 Introduction

In this paper we attempt to further the theory of the “second eigenvalue” of hypergraphs. The theory of the second eigenvalue of graphs is very rich, and can be used to give explicit constructions of graphs with certain geometric properties. However, its applications to problems such as constructing dispersers seem rather limited. This construction method generalizes naturally to hypergraphs, and, in fact, constructing hypergraphs with small second eigenvalue can give much better dispersers (see [FW89]).

∗This paper was written while the author was visiting ICSI. The author also wishes to acknowledge the National Science Foundation for supporting this research in part under a PYI grant, CCR–8858788.

The problem with the notion of second eigenvalue for hypergraphs, as in [FW89], is that much of the eigenvalue theory for graphs does not generalize. For example, the “second eigenvalue” is not really an eigenvalue in any classical sense, and it is not clear that the known constructions of graphs with small second eigenvalue generalize in a strong way (e.g. to give better dispersers that can be given via graphs). In addition, there are various ways one can try to study the second eigenvalue of hypergraphs by relating them to the second eigenvalue of certain graphs^{1}, but the ones with which the author is familiar do not give, for example, better dispersers.

In graph theory, there is a strong connection between the second eigenvalue of a d-regular graph and the first eigenvalue of the infinite d-regular tree, its universal cover. In this paper we define for a uniform and regular hypergraph an infinite hypertree, and we analyze the “first eigenvalue” of the infinite hypertree. We do this for two notions of “first eigenvalue” or spectrum, but only for the first do we determine the precise answer. The analysis shows that, as with graphs, the second eigenvalue of random, regular hypergraphs is roughly the same as the first eigenvalue of the corresponding infinite hypertree; also, this value is roughly as small as one can get with any hypergraph of the same regularity.

The first notion of spectrum is the direct generalization of the definition in [FW89], but the second notion is new and perhaps has more structure to it. In particular, for every value of λ we define what it means to be spectral or non-spectral. In the first notion there is only a notion of what the “largest eigenvalue” would be, or “second largest” for a finite regular hypergraph.

While the theorems proven here are fairly simple and don’t directly imply facts about finite hypergraphs, the analysis does seem to show that there may be more ways to study “eigenvalues” of hypergraphs. Namely, there is a natural notion of universal cover for hypergraphs, and its spectrum is, at least for superficial reasons, related to the spectrum of the finite hypergraphs it covers. In doing so, we introduce a new notion of spectrum, which may be worthy of study. The author hopes that the continued study of the spectra of hypergraphs will eventually yield explicit constructions of finite hypergraphs with small second eigenvalues.

1The author wishes to thank F. Bien and E. Shamir for useful conversations on this point.

In section 2 we discuss the relationship between the spectra of regular graphs and the corresponding infinite trees. In section 3 we define hypertrees and study their spectra. In section 4 we make some remarks about further directions of study.

The author wishes to thank Frederic Bien, Peter Sarnak, and Eli Shamir for useful discussions.

2 The Spectrum of Graphs and Infinite Trees

In this section we summarize the connection between the spectrum of graphs and infinite trees, and we state two definitions of spectrum which can be generalized to hypergraphs, the one in [FW89] and one new one.

Let G = (V, E) be a finite, undirected, d-regular graph, i.e. with every vertex having degree d, and let A be its adjacency matrix. Then A is an n×n matrix, n = |V |, which is symmetric and therefore has real eigenvalues λ_{1} ≤ λ_{2} ≤ ⋯ ≤ λ_{n}. It is easy to see that λ_{1} = d and that λ_{n} ≥ −d. There are examples of graphs (see [LPS86], [LPS88], [Mar84], [Mar87], [Mar88], [Hal86], [Chu88], and [Fri89]), for certain values of d and n, for which

λ_{i} ∈ [−2\sqrt{d − 1}, 2\sqrt{d − 1}]  ∀i ≥ 2,  (2.1)

and it is easy to show that for fixed d and n → ∞ the interval in the above equation cannot be replaced by any smaller interval (independent of n; for d varying with n one can do better, as in the last three references). It is also known that, for fixed d, “most” d-regular graphs on n vertices satify equation 2.1 if we enlarge the interval by an additive factor of 2 log d + C on each end, for some constant C, as n → ∞ (see [Fri88]).

Next let T = (W, F) be the undirected, infinite, d-regular tree. We view its adjacency matrix as an operator B on L^{2}(W), and it is easy to see that the spectrum of B is precisely the interval appearing in equation 2.1 (see [Car72] and the many references in [DK88]). This is not a coincidnece, in that there is a standard technical reason for the similarity in the two, involving taking the trace of powers of A while viewing T as the universal cover of G. For example, the additional eigenvalue d which occurs in A’s spectrum accounts for the fact at the m-th level of T, viewing T as rooted with root r, for large m one expects roughly 1/n of the nodes to be the same V node as r; the deviation from this behavior is precisely related to the second eigenvalue of G (see, for example, [Fri88]).

Much of the theory used with graphs, such as forming matrices and considering their eigenvalues (via taking traces, etc.) seems to be difficult to generalize in a way that gives good results for the second eigenvalue of hypergraphs. We will give some definitions and propositions which generalize more directly for the infinite tree.

We begin with the standard calculation of the spectrum of the tree. We include the proof because it will be used in the hypergraph analysis.

Proposition 2.1 The spectrum of B as above is [−2\sqrt{d − 1}, 2\sqrt{d − 1}].

Proof Fix a vertex v of T. Consider the “radial” function f_{r}: T → C whose value at the m-th level of T, i.e. at all vertices of distance m to v, is r^{m}. We have that

((B − λI)f_{r})(w) = \{ \begin{matrix}dr − λ & if w = v, \\ r^{m−1}((d − 1)r^{2} − λr + 1) & if w lies on level m ≥ 1. \end{matrix}

Fix a λ with |λ| > 2\sqrt{d − 1}. There exists a solution, r, to

(d − 1)r^{2} − λr + 1 = 0  (2.2)

with |r| < (d − 1)^{−1/2}, which makes the resulting f_{r} lie in L^{2}(W). For such an r we have dr − λ ≠ 0, and therefore the equation in x,

(B − λI)(x) = δ_{v}  (2.3)

has an L^{2}(W) solution x, where δ_{v} is 1 on v and 0 elsewhere. Writing an arbitrary w ∈ L^{2}(W) as a (possibly infinite) linear combination of such δ’s and using linearity, we can solve the above equation in x with δ_{v} replaced by any w, with ∥x∥ bounded by a constant times ∥w∥. Therefore B − λI is invertible and λ lies outside the spectrum of B.

On the other hand, we claim that for |λ| < 2\sqrt{d − 1}, equation 2.3 has no solution x ∈ L^{2}(W). Indeed, if such an x existed, then its symmetrization, x̃, whose value at each vertex on the m-th level is the average of the m-th level value of x, would also be an L^{2}(W) solution of equation 2.3. Then the values x̃_{i} of x̃ at the i-th level satisfy

(d − 1)x̃_{i+2}^{2} − λx̃_{i+1} + x̃_{i} = 0 ∀i ≥ 0,

and so

x̃_{m} = c_{1}r_{1}^{m} + c_{2}r_{2}^{m}

for some constants c_{i} and with r_{i} being the roots of equation 2.2. But for λ the roots r_{1}, r_{2} are both of absolute value (d − 1)^{1/2}, contradicting the fact that x̃ ∈ L^{2}(W).

Also λ = ±2\sqrt{d − 1} is in the spectrum, either by modifying the equation for x̃_{m} in the above, or by noting that the spectrum is a closed set. Since B is self-adjoint its spectrum is real, we have now determined its entire spectrum.

□

Since B is self-adjoint, the above proposition implies the following.

Corollary 2.2 For any x, y ∈ L^{2}(W), |(Bx, y)| ≤ 2\sqrt{d − 1}∥x∥ ∥y∥, and 2\sqrt{d − 1} is the best constant possible. Equivalently, the L^{2}(W) norm of B is 2\sqrt{d − 1}.

We provide a simpler proof of this which immediately generalizes to hypertrees. The upper bound is, in a sense, related to “integration by parts” eigenvalue bounds suggested to the author by P. Sarnak. Proof It suffices to consider the case ∥x∥ = ∥y∥ = 1. We have

(Bx, y) = ∑_{(i,j)∈F} x_{i}y_{j},

where we think of F as containing one copy of (i, j) and one of (j, i) for every undirected edge {i, j} in contains. For those terms x_{i}y_{j} in the above sum with i nearer to v than j, write

x_{i}y_{j} ≤ \frac{1}{2} (\sqrt{d − 1}x_{i}^{2} + y_{j}^{2}/\sqrt{d − 1});

for those with j nearer to v, reverse x_{i} and y_{j}. Remembering that every vertex except v has one neighbor closer to v and d − 1 further from v (and that v has d neighbors, all further away from v), we get

|(Bx, y)| ≤ ∑_{w∈W −\{v\}} 2\sqrt{d − 1}(x_{w}^{2} + y_{w}^{2}) + \frac{d}{\sqrt{d − 1}}(x_{v}^{2} + y_{v}^{2}) ≤ 2\sqrt{d − 1}.

This provides an upper bound on the norm of the bilinear form associated with B. For the lower bound, condiser for small ϵ > 0 the radial function, f_{r}, with r = (d − 1)^{−1/2}(1 − ϵ). We have

∥f_{r}∥^{2} = 1 + ∑_{m=1}^{∞} d(d − 1)^{m−1} ((d − 1)^{−1/2}(1 − ϵ))^{2m} = \frac{d}{d − 1} \frac{1}{2ϵ} + O(1),

and, similarly,

(Bf_{r}, f_{r}) = \frac{2d}{\sqrt{d − 1}} \frac{1}{2ϵ} + O(1),

so that taking ϵ → 0 gives the desired lower bound.

□

The above argument also shows that the norm of B is never acheived by any vector in L^{2}(W). We now state the precise definitions which we intend to carry over to hypergraphs in the next section. In what follows we take L^{2}(W) to be the space of complex-valued functions, although in a lot of places it suffices to take real-valued functions.

Definition 2.3 The spectral radius of the infinite tree, T, with adjacency matrix B is the L^{2}(W) norm of the bilinear form (Bx, y).

Definition 2.4 For the infinite tree, T, with adjacency matrix B, a number λ ∈ C is said to be non-spectral if

(i) Fundamental solutions exist for B − λI, i.e. there exists an x with (B − λI)x = δ_{v},

(ii) for every y ∈ L^{2}(W), (B − λI)x = y has a solution x ∈ L^{2}(W),

(iii) the above x is uniquely determined,

(iv) the above x’s norm is bounded by a constant times y’s.

If any of the above fail to hold, λ is said to be spectral. Also, a λ ∈ R is said to be a spectral upper bound (respectively, lower bound), if it is non-spectral and

(i) for every real-valued x, y pair with (B − λI)x = y, we have (x, y) is non-negative (respectively, non-positive).

Note that in the present circumstances, the first condition of non-spectrality implies all the others.

3 The spectra of hypergraphs and infinite hypertrees

For simplicity we will state all theorems in this section for 3-uniform hypergraphs, though all the theorems here easily generalize to t-uniform hypergraphs for any fixed t.

We review our terminology for hypergraphs; see [FW89] for details. A 3-uniform hypergraph is a collection G = (V, E) of a set V and a collection of subsets of V, E, such that each subset e ∈ E has size three. Out of this data we can form a trilinear form τ analogous to the bilinear form associated to the adjacency matrix of a graph, namely

τ(x, y, z) = ∑_{i,j,k∈V} x_{i}y_{j}z_{k}τ_{ijk}

for x, y, z ∈ L^{2}(V), where

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

For our purposes it is simpler to think of a hypergraph as a trilinear form, τ, with τ_{ijk} non-negative integers. In [FW89] the second eigenvalue of τ is defined to be

∥τ − \frac{d}{n}E∥,  (3.1)

where E is the trilinear form with all E_{ijk} = 1, n = |V |, d = ∑_{ijk} τ_{ijk}/n^{2}, and the norm is the norm as a trilinear form on L^{2}(V), i.e.

∥σ∥ = max_{∥x∥=∥y∥=∥z∥=1} |σ(x, y, z)|.  (3.2)

It is shown there that for a “randomly chosen” τ on n vertices with dn^{2} hyperedges, d > C log n, the second eigenvalue of τ is, with high probability, roughly \sqrt{d}, to within a factor of C(log n)^{3/2}. This can be compared with its “first eigenvalue,” namely the norm of τ, which is roughly d\sqrt{n}. One can give explicit examples of hypergraphs with second eigenvalue around d^{1/2}n^{1/4}, but this does not give improvements for the disperser construction. However, any explicit construction of hypergraphs with smaller exponents would yield improvements.

First we form a notion of the infinite hypertree. Before doing so, notice that the first and second “eigenvalues” of a random τ (as above) are not powers of each other. We can remedy this by working with the L^{3}(V) norm. Indeed, as remarked in [FW89], all the theorems generalize to L^{p} for any p (using equaiton 3.1, but taking ∥ · ∥ on x, y, z to be the L^{p}(W) norm in equation 3.2), and choosing p = 3 gives first eigenvalue (i.e. norm of τ) to be roughly dn and second eigenvalue to be roughly (dn)^{1/3}. While the L^{3} norm may seem strange, it has other advantages. For one thing, defining eigenvalues in terms of bilinear forms involves picking a fixed inner product on the space in question. A natural analogous trilinear product is

I(x, y, z) = ∑_{i∈V} x_{i}y_{i}z_{i},

and when using I it seems natural to work with the L^{3} norm. Also, use of the L^{3} norm suggests that we work with k = dn as the “degree” of our hypergraph, and this notion of degree gives a good model of a universal cover.

To define our hypertree, fix a value of k. Start by taking one triangle, and to each of its vertices glue k − 1 triangles, all disjoint except that they meet in the one vertex. For each newly created vertex create k − 1 new triangles. The resulting infinite hypergraph, T = (W, F) is depicted in the figure 1. On T we have a notion of distance, defining two vertices to be neighbors (i.e. distance 1) if they both lie in some triangle. Thus, if the top vertex of the figure 1 is v, then all the vertices of distance one to v lie in the row of vertices directly below v, those of distance two in the next row, etc.

We call the above hypergraph, T, the k-regular hypertree. Why do se use this model? Aside from the fact that the first and second L^{3} eigenvalues of a random hypergraph are roughly powers of k, this hypertree is, in

[figure: v; .; .; .; .  .  .; ...; ...; ...; .  .  .]

Figure 1: The Infinite Hypertree a natural way, the universal cover of any hypertree of degree k, i.e. in which each vertex is incident on exactly k (hyper)edges. More precisely, taking a morphism of hypergraphs to be a map of vertices which maps edges to edges, and a cover to be a locally invertible morphism, our kregular tree is precisely a (the) universal cover. In particular, any finite hypergraph of degree k is isomorphic to a quotient of our hypertree modulo some equivalence relation on the vertices We could have constructed the hypertree by growing triangles off of edges, requiring that each edge meet d trianlges; this would be closer to the definition of regularity appearing in [FW89], but seems to be harder to work with.

The infinite hypertree, T, has a trilinear form τ associated to it via the above proceedure, in which each triangle gives rise to six 1’s in τ. We expect, in analogy with the infinite tree, that the range of the L^{3} “spectrum” of τ, appropriately defined, should be roughly k^{1/3}, i.e. what the second eigenvalue is for a random hypergraph. Similar to the “eigenvalue” definitions in [FW89] we make the following definition.

Definition 3.1 The spectral radius of a trilinear form is its L^{3} norm.

Proposition 3.2 The spectral radius of τ, i.e. its L^{3}(W) norm, is 3(2k − 2)^{1/3}.

Proof Fix a vertex, v, in T. Each triangle is of the form, {i, j, l}, with i a vertex of distance m to v, and j, l of distance m + 1 to v for some m. To estimate τ(x, y, z) for vectors x, y, z of norm 1, we can estimate for any positive γ

|x_{i}y_{j}z_{l}| ≤ \frac{1}{3} (γ^{−2/3}|x_{i}|^{3} + γ^{1/3}|y_{j}|^{3} + γ^{1/3}|z_{l}|^{3})

and similarly for the other five terms arising from {i, j, l}. Then summing as before yields

|τ(x, y, z)| ≤ max (2γ^{1/3} + 2(k − 1)γ^{−2/3}, 2kγ^{−2/3}) ,

the first term in the max accounting for the contribution of vertices in W −{v}, the second for v’s (i.e. the components of x, y, z at these vertices). Taking γ = (2k − 2)^{1/3} yields the desired upper bound on ∥τ∥.

On the other hand, let f_{r} be the function on W whose value at each vertex of distance m to v is r^{m}. Then for small ϵ > 0 and r = (2k − 2)^{−1/3}(1 − ϵ) we have

∑_{w∈W} f_{r}^{3}(w) = \frac{k}{k − 1} \frac{1}{3ϵ} + O(1),

and

τ(f_{r}, f_{r}, f_{r}) = 6k(2(k − 1))^{−2/3} \frac{1}{3ϵ} + O(1),

so that

∥τ∥_{L^{3}(W)} = 6 · 2^{−2/3}(k − 1)^{1/3} = 3(2k − 2)^{1/3}.
□

Next we consider the analog of definition 2.4. The equation (B−λI)x = y can be written as

B(x, w) − λ(x, w) = (y, w)  ∀w ∈ L^{2}(W),  (3.3)

where B(x, w) = (Bx, w) is the bilinear form associated with B. To generalize this to hypergraphs, note that we have a natural trilinear form τ to replace B, and the question becomes what to use for the standard inner product, ( · , ·). For the latter we suggest using the above defined I. The trilinear form I seems the most natural to use, although it does have all the nice properties of the standard bilinear inner product, for example I(u, u, u) is not generally = ∥u∥^{3}. However using I does seem related to our previous notion of spectral radius.

The question now is how many fixed variables, such as x or y, to use in an analog of equation 3.4, and how many test variables, such as w, to use and where to place them. In this paper we investigate the equation

τ(x, x, u) − λI(x, x, u) = I(y, y, u)  ∀u ∈ L^{3}(W).  (3.4)

Arguably we should replace x and/or y by two variables, but we leave it in this form for simplicity and recalling that if τ is symmetric then to find its norm it suffices to check τ(x, y, z) for x = y = z.

We pause to make two remarks about I. First of all, for any x, y, z ∈ L^{3}(W),

|I(x, y, z)| ≤ ∥x∥ ∥y∥ ∥z∥;

this follows from two applications of Hölder’s inequality or estimating as in the proof of proposition 3.2. Secondly, for any x ∈ L^{3}(W) we use the notation x′ to denote the vector given by |x′_{w}| = |x_{w}| and x′_{w}x_{w}^{2} = |x_{w}|^{3}. Thus x′ differs pointwise from x by numbers of absolute value 1, has the same norm as x, and satisfies

I(x, x, x′) = ∥x∥^{3}.

Definition 3.3 For a trilinear form, τ, a number λ ∈ C is said to be non-spectral if

(i) Fundamental solutions exist for τ − λI, i.e. there exists a solution x for equation 3.4 with y = δ_{v},

(ii) for every y ∈ L^{3}(W), equation 3.4 has a solution x ∈ L^{3}(W),

(iii) any solution, x, for (ii), has its norm bounded by a constant times y’s,

If any of the above fail to hold, λ is said to be spectral. Also, a λ ∈ R is said to be a spectral upper bound (respectively, lower bound), if it is non-spectral and

(i) for every pair x, y satisfying equation 3.4 and with x real and each y_{w} either real or purely imaginary, we have I(y, y, x′) is non-negative (respectively, non-positive).

We have omitted the condition that x is uniquely determined, since this will never be the case (see below). As before, L^{3} refers to complex valued functions; it is not clear that real L^{3} works as well here (for λ real). In the definition of spectral upper and lower bounds, we have allowed some of y’s values to be purely imaginary to make sure that every real x has a corresponding y (see equation 3.5 below).

We now state the main result of the paper, whose proof comprises the rest of this section.

Theorem 3.4 Any λ ∈ C with absolute value bigger than the spectral radius is non-spectral. In particular, any such positive (respectively, negative) λ is a spectral upper (lower) bound.

To begin the analysis, notice that equation 3.4 is equivalent to requiring that for all w ∈ W,

∑_{j=1}^{k} x_{α(w,j)}x_{β(w,j)} − λx_{w}^{2} = y_{w}^{2},  (3.5)

where each α( · , l) and each β( · , l) is a permutation of W.

We will first discuss in detail the situation for real λ, and remark later about complex λ.

We claim that almost every real λ has a complex-valued fundamental solution. That is, letting f_{r} be as before, we see from equation 3.5 that f_{r} will be a fundamental solution iff

(k − 1)r^{3} − λr + 1 = 0.

Proposition 3.5 The equation s^{3} − αs + 1 = 0 has

1. all roots of absolute value 1 if α = 0, 2;

2. one positive real root of absolute value < 1, two complex roots of absolute value > 1 if α < 0;

3. one negative real root of absolute value < 1, two real roots of absolute value > 1 if α > 2;

4. one real root of absolute value > 1, two complex roots of absolute value < 1 if 0 < α < (27/4)^{1/3};

5. one real root of absolute value > 1, two real roots of absolute value < 1 if (27/4)^{1/3} ≥ α < 2 (the latter two roots being a double root when equality holds).

Proof Follows easily from the fact that the above equation has discriminant 4α^{3} − 27 and that g(s) = s^{3} − αs + 1 has g(−1) = α and g(1) = 2 − α.

¿From this proposition it follows that there is always a radial fundamental solution, f_{r} ∈ L^{3}(W), except for r = 0, 2(k − 1)^{1/3}. The existence of a solutions to equation 3.4 does not follow, because of the non-linearity. However, assuming that λ is larger than the spectral radius, one can solve equation 3.4 for any finitely supported y (i.e. which is zero at all but a finite number of vertices), and pass to the limit for general y. In proving both steps we will use the estimate in the (direct) proof of corollary 2.2, and we do not know what happens in general.

[figure: 1; x; 2; r; 1; x; 2; r; 2k; 2k; 2; 2; 2; rx; rx; rx; rx; rx; 1; rx; 1; 1; rx; 1; rx; 2k; x; 2k-1; x; 4; x; 3; x; 2; x; 1; x; 0; x; rx; .; .; .; .  .  .; ...; ...; ...; .  .  .]

Figure 2: A general solution x for m = 1.

Theorem 3.6 Let |λ| > 3(2k − 2)^{1/3}. Then for any finitely supported y there exists a solution, x, to equation 3.4.

Proof As usual, fix a vertex v. Suppose y is supported on the set of vertices of distance ≤ m to v. Consider the class of vectors, x, whose values at the vertices of distance ≤ m is arbitrary, and whose values at each vertex of distance ≥ m+1 is given as r times the value of its neighbor which is closest to v. Such x are “eventually radial;” we have depicted the case m = 1 in figure 2. For any such x it is clear that equation 3.5 holds for any w of distance ≥ m + 1 from v. To satisfy this equation at the other w’s, we get N quadratic equations in the N variables x_{w} where w ranges over the vertices on levels ≤ m. It follows that the system of equations has at least one solution in x over N-dimensional (complex) projective space^{2}. But it is easy to check that all solutions of these N equations lie in affine space. This is because a solution in projective space is precisely a non-trival solution, x, of the same system with the y_{i}’s replaced by zeros. But this would imply

τ(x, x, u) − λI(x, x, u) = 0 ∀u ∈ L^{3}(W).

In particular, choosing x′ ∈ L^{3}(W) given by |x′_{v}| = |x_{v}| and x′_{v}x_{v}^{2} = |x_{v}|^{3} we get

|λ|∥x∥^{3} = |λI(x, x, x′)| = |τ(x, x, x′)| ≤ 3(2k − 2)^{1/3}∥x∥^{3},

which contradicts the non-triviality of x. Hence all projective solutions of the aforementioned system lie in affine space, and so there exists at least one such solution.

□

We mention, as in the footnote, that the solvability of equation 3.4 for arbitraty y is related, in a certain sense, to the non-existence of non-trivial solutions for the special case y = 0. We will return to this point in the next section.

Theorem 3.7 Let |λ| exceed the spectral radius. Then for any y ∈ L^{3}(W), there exists a solution x ∈ L^{3}(W) to equation 3.4. Furthermore, for any such solution x, we have ∥x∥ ≤ C∥y∥, where C depends only on |λ|.

Proof A priori, for any solution x as above we have

τ(x, x, x′) − λI(x, x, x′) = I(y, y, x′),

so that

(|λ| − 3(2k − 2)^{1/3}) ∥x∥^{3} ≤ |I(y, y, x′)| ≤ ∥y∥^{2}∥x∥.

2see, for example, [Har77], I.7.2. The reader who is unfamiliar with algebriac geometry can recall that if an N × N linear system Ax = 0 has no non-trivial solutions, x, then for any b the system Ax = b has a solution. This turns out to be true if the linear equations are replaced by any homogeneous equations, assuming the underlying field is algebraically closed. This is the point of making the calculation which follows.

Hence

∥x∥ ≤ C∥y∥ for C = (|λ| − 3(2k − 2)^{1/3})^{−1/2} .

Now fix y ∈ L^{3}(W), and let y^{n} be a sequence of finite truncations of y converging to y, i.e. y^{n} are finitely supported, y_{w}^{n} is either 0 or y_{w} for each n and w, and ∥y^{n} − y∥ → 0 as n → ∞. For each n choose a solution x^{n} to equation 3.4 for y^{n}. Since ∥y^{n}∥ is bounded, so is ∥x^{n}∥, and any weakly converging subsequence of the x^{n}’s gives us a solution, x, to equation 3.4.

In more detail, for each w, the sequence x_{w}^{n} is bounded, and so we can assume, by passing to a subsequence, that for each w ∈ W we have x_{w}^{n} → x_{w} for some x_{w} ∈ C (since W is countable, using a “diagonal subsequence”). A standard argument shows that the resulting vector x lies in L^{3}(W): let x̃ be any truncation of x. Then x̃ ∈ L^{3}(W), and

I(x̃, x̃′, x^{n}) ≤ ∥x̃∥^{2}∥x^{n}∥.

Taking any subsequence of n’s tending to infinity, the left-hand-side converges to ∥x̃∥^{3}, and so

∥x̃∥ ≤ lim inf ∥x^{n}∥.

Since this holds for any truncation, x̃ of x, this holds for x itself. Finally, for each w, equation 3.5 holds for x and y, since for all sufficiently large n (depending on w) the equation holds for x^{n} and y, and this equation involves only terms x_{v}^{n} with v ranging over a finite set. Hence x is a solution to equation 3.4, and it clearly satisfies the a priori bound given.

□

To complete the proof of theorem 3.4, it is clear that in general any real positive (respectively, negative) λ which is spectral and which exceeds the spectral radius must be a spectral upper (lower) bound. Finally, the entire discussion of non-spectrality goes through for λ ∈ C of absolute value exceeding the spectral radius, with minor modifications. We start by observing that the equation

s^{3} − αs + 1 = 0

can only have all roots, s_{1}, s_{2}, s_{3} of absolute value ≤ 1 if

|α| = |s_{1}s_{2} + s_{1}s_{3} + s_{2}s_{3}| ≤ 3;

This implies that any complex λ with |λ| > 3(k − 1)^{1/3} has a fundamental solution. The rest of the analysis goes through virtually word for word, to show that λ’s with |λ| > 3(2k − 2)^{1/3} are non-spectral.

□

We remark that we never have uniqueness in equation 3.4. One obvious reason is that if x is a solution then so is −x. However, this is not the only source of non-uniqueness. For example, if the support of x ∈ L^{3}(W) is any set of minimum distance 3, i.e. the distance between any two distinct vertices is at least 3, then there is a y ∈ L^{3}(W) which satisfies equation 3.4, and any pattern of sign changes in x yields another solution. So, in general, there can be an infinite number of solutions, x, for a given y.

4 Finite versus infinite hypergraphs

We finish with some remarks on the question of constructing finite hypergraphs with small second eigenvalues.

The basic question is to construct hypergraphs on n nodes with dn^{2} edges whose second eigenvalue, measured in L^{3}, is roughly (dn)^{1/3}. For the application to dispersers, it would be desirable that the hypergraph be constructable in poly-logarithmic time in n and d. So, for example, in the analogous construction problem for graphs, the graphs given in [LPS86] and [Mar84] are not known to be constructable so quickly, but those of [Hal86], [Chu88], [Fri89] are. Any construction yielding a hypergraph of second L^{3} eigenvalue ≤ (dn)^{β} for some β < 1/2 would improve the best disperser construction known at present; for example, it could boost ϵ-weak sources for some ϵ < 1/2.

Clearly any symmertric, regular hypergraph can be represented as the quotient of an infinite tree whose vertices are identified in some way. The question becomes, then, are there concise properties of the universal covers which control the second eigenvalue of a finite hypergraph?

We can suggest the following question, which is even interesting for graphs. Given a finite graph and an eigenvector, is there a direct way to prove its eigenvalue is small by associating to it some vector, or perhaps probability space of vectors, on its universal cover? This association should work for all vectors perpendicular to e = (1, 1,…, 1) but not for e itself, and would have to involve some properties of the map from the universal cover to the graph (since no good bound holds for all finite graphs). This is a suitably vague question, but the intention is to develop methods that could carry over to hypergraphs to yield better second eigenvalue bounds.

For finite hypergraphs, one may be able to define notions of spectrality as in definition 3.3, but one would probably want to modify the definition. For example, consider the following consequence of the standard variational argument.

Proposition 4.1 Let τ be a symmetric, trilinear form on L^{3}(V), where V is a finite set, and let E be a linear subspace of L^{3}(V). If |τ(v, v, v)| over unit vectors v ∈ E is maximized at v = x, then there is a λ′ such that

τ(x, x, u) − λ′I(x, x, u) = 0 ∀u ∈ E.

Proof If I(x, x, u) = 0, it follows that τ(x, x, u) = 0 by considering |τ(v, v, v)| with v = x + ϵu and ϵ small. So choosing λ′ to make the above equation hold for any particular u with I(x, x, u) ≠ 0 will work.

□

The point is here is that for λ′ to equal λ it is necessary that |I(x, x, x)| = ∥x∥^{3}, which will not generally be the case. A solution to the above equation is clearly related to the solvability of equation 3.4 for λ = λ′ (i.e. too many solutions to the above prohibits a solution to equation 3.4), but we wouldn’t expect λ and λ′ to agree over, for example, the subspace, E, of u’s with I(1,1, u) = 0, where 1 is the all 1’s vector. Hence, to study an analog of definition 3.3 for the second eigenvalue of finite hypergraphs, we would expect some modification.

We remark that all the theorems stated in section 3 generalize easily to t-uniform hypergraphs, which are collections, G = (V, E) where each e ∈ E is a subset of size t. The resulting eigenvalue for the k-regular, t-uniform hypertree is (k − 1)^{1/t}t!(t − 1)^{(1−t)/t}, which for fixed k is within poly-log factors in k of the right answer, i.e. of the lower bound and of the upper bound for random hypergraphs.

References

[Car72] P. Cartier. Functions harmoniques sur un arbre. Symposia Math., 9:203–270, 1972.

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

[DK88] J. Dodziuk and L. Karp. Spectral and function theory for combinatorial laplacians. In Geometry of Random Motion (Ithaca, NY, 1987), pages 25–40. Amer. Math. Soc, 1988.

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

[FW89] J. Friedman and A. Wigderson. On the second eigenvalue of hypergraphs. Technical report, Princeton University, September 1989.

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

[Har77] Robin Hartshorne. Algebraic Geometry. Springer-Verlag, 1977.

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

[LPS88] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261–277, 1988.

[Mar84] G.A. Margulis. Arithmetic groups and graphs without short cycles. In 6th Inter. Symp. on Information Theory, Tashkent, Abstracts, Vol. I, pages 123–125, 1984. (In Russian).

[Mar87] G.A. Margulis. Some new constructions of low-density paritycheck codes. In 3rd Inter. Sem. on Information Theory, convolution codes and mulit-user communication, Sochi, pages 275–279, 1987. (In Russian).

[Mar88] G.A. Margulis. Explicit group theoretic constructinos of combinatorial schemes and their applications for the constructions of expanders and concentrators. J. of Prob. of Information Transmission, 1988. (In Russian).