Some Graphs with Small Second Eigenvalue

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

October 12, 1989

1 The Second Eigenvalue of a Hypergraph

In this section we will first define the second eigenvalue of 3-regular hypergraph, and then discuss the general notion, as it applies to other regular 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-regular 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-degree-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-regular 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-degree-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-degree-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-degree-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-degree-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-degree-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-regular hypergraphs. There is a lot of structure for graphs that we don’t know how to carry over to 3-regular hypergraphs. For example, we don’t know how multiply two hypergraphs. However, a fair amount of the theory for graphs can be generalized to 3regular hypergraphs. We will prove:

Theorem 1.1 The first eigenvalue of a d-degree-regular 3-regular 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-regular, d-degree-regular hypergraph has second eigenvalue ≥ \sqrt{d}.

Theorem 1.4 For any d and n, a random d-degree-regular 3-regular hypergraph on n vertices has second eigenvalue ≤ C\sqrt{d} for some absolute constant C.

All of the above theorems have generalizations to r-regular hypergraphs. The last theorem is quite interesting, in that implies the existence of hypergraphs with such low second eigenvalues that they could significantly improve on a class of applications of graphs with low second eigenvalues. Unfortunately we do not have an explicit construction for such hypergraphs. Most explicit constructions of graphs with small second eigenvalues are Cayley graphs of some sort. There is a natural generalization of these graphs, which we call “Cayley hypergraphs,” but it turns out that these hypergraphs can never have such low second eigenvalues as those of theorem 1.4. We will discuss Cayley hypergraphs in section mumble. We also discuss second eigenvalue for bipartite graphs, but this does not yield anything new applications.

2 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-degree-regular if it satisfies the conditions mumble.

Theorem 2.1 Let τ be a non-negative, d-degree-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, θ-degree-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 2.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 2.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 2.4 Let H be a k-regular, d-degree-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 2.5 Let H be as in proposition 2.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 d-regular graph, and can therefore apply lower bounds known for the second eigenvalue of graphs. The preceding proposition is an example. There are two other methods for obtaining lower bounds, and they yield:

Proposition 2.6 Mumble.

Proposition 2.7 Mumble.

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], [?], [FW]. However the method of Kahn and Szemeredi, in [KS], does generalize quite readily, and we can prove:

Theorem 2.8 Mumble

Proof Mumble.

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. 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 σ_{1},…, σ_{n} be any set of n permutations on the numbers {1,…, n} with the property that for any i,

{σ_{1}(i),…, σ_{n}(i)} = {1,…, n}.

Let G̃ = (V, Ẽ) we the 3-regular hypergraph with edge set

Ẽ = {(i, j, k) | (j, σ_{i}(k)) ∈ E}.

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

Proof Mumble.

3 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 dregular 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 [?] 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 3.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}|.

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

□

References

[FW] J. Friedman and A. Wigderson. On the second eigenvalue of hypergraphs. To appear.

[KS] J. Kahn and E. Szemeredi. Personal communication, and to appear.

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

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

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