Relative Expansion and an Extremal Degree Two Cover of the Boolean Cube

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

November 30, 1995

Abstract

In this paper we show that there is a unique degree two cover of the Boolean ncube whose new eigenvalues are all ±\sqrt{n}, and we describe some of its properties. To explain it further, we develop relative notions of expansion and relate them to the new eigenvalues. We will give examples of the importance of covering maps. We also explain how these properties generalize to pregraphs.

Then we perform some numerical calculations which suggest that no such covers exists for general covers of higher degree. The new eigenvalues of degree two covers gives a geometric interpretation of the eigenvalues of “signed graphs.”

1 Introduction

In this paper we then describe certain relative notions in graph theory, such as those which generalize the absolute notions of “expansion” and “having small second eigenvalue;” we will primarily be interested in relative notions where the underlying morphism is a covering map (of graphs). We also describe an interesting degree two cover of the Boolean cube, which has extremal eigenvalue properties in that all its new eigenvalues have the same absolute value.

This paper began as an attempt to further study the Fourier analysis of Boolean functions. There are many properties of this analysis which could be important to understand, such as the extent to which Fourier coefficients can cancell under convolution (see [CFG^{+}85],[Fri92]). As is well-known in number theory and geometry, certain properties of objects often become much clearer when passing to covers of the object, and at times even understanding an object’s cyclic covers suffices to elucidate certain situations.

∗The author also wishes to acknowledge the National Science Foundation for supporting this research in part under a PYI grant, CCR–8858788.

For this reason we wished to study how the Fourier analysis changes when passing to a cover of the Boolean n-cube (i.e. B^{n}, the graph with vertices {0, 1}^{n}, and edges between any two vertices which differ from each other in exactly one component. Fourier analysis can be viewed as a refinement of studying the adjacency matrix of B^{n}, and so, as a first attempt to study how the Fourier analysis generalizes, the author made a numerical study of the eigenvalues of degree two covers of B^{n}. (It is only in special situations, namely where the cover is a Cayley graph, that one can study the “Fourier analysis” of the cover, i.e. the representations of the underlying group.)

This numerical study suggested the existence of an extremal degree two cover of B^{n} with respect to the new eigenvalues, which we will prove.

Theorem 1.1 There exists a unique degree two cover of the Boolean n-cube, such that all its new eigenvalues are of absolute value \sqrt{n}. All other covers have at least one new eigenvalue of absolute value > \sqrt{n}.

This property is also understandable in terms of a relative notion of expansion, this extremal cover being the best relative expander of the Boolean cube among all degree two covers.

In section 2 we prove the existence of the extremal degree two cover of the Boolean cube and describe some of its properties. In section 3 we discuss several relative notions concerning eigenvalues and expansion, and prove theorems relating them. In section 4 we discuss how such notions carry over to pregraphs (which are necessary in developing a covering theory of undirected graphs and some covering theories of graphs). In section 5 we give some tables of eigenvalues of cyclic covers of small degree of the Boolean cube of small dimension. A review of pregraphs and their importance to covering theory is described in appendix A. In appendix B we describe some notions about measures and functions on graphs developed in [Fri93] which will be referred to in section 4.

Next we describe some conventions used throughout this paper. If G is a graph, we denote its vertex set and edge set by V (G) and E(G). For A, B ⊂ V (G), E(A, B) denotes the subset of edges with one endpoint in A and one in B, and e(A, B) denotes its size.

By a function on a graph G we mean a function on its vertices. Functions, unless otherwise specified, are real-valued. A function on G can be viewed as a function defined on the edges, in a manner described in appendix B.

By a graph we mean an undirected graph, which can have multiple edges, selfloops, and half-loops : more precisely, an undirected graph, G, is a directed graph, G′, with an involution σ: G′ → G′ (i.e. σ^{2} = the identity) with σ the identity on vertices and reversing edge orientation (and preserving incidence relations); all standard graph notions generalize to graphs in this (more general) sense; the only new feature in this definition of graphs is that σ can map a self-edge in G′ to itself, which results in a loop from a vertex to itself in the graph of valence one, which we refer to as a half-loops (see [Fri93]). (The above does not affect our discussion of the Boolean cube and its covers.)

When dealing with directed graphs, B_{d} refers to the graph with one vertex and d self-loops. With graphs, B_{d} refers to the graph with one vertex and d half-loops.

We conclude by remarking that Noga Alon has suggested to the author that one might be able to construct new expanders by starting with a (simple) relative expander and forming an appropriate quotient. The number of nodes of the quotient graph would presumably be the degree of the original covering, and so one would have to study higher degree coverings (than degree two). It would be interesting to (successfully) persue this further. The author wishes to thank Noga, as well as Laci Lovász, David Goldschmidt, and Michael Hirsch for helpful discussions.

2 An extremal cover of degree 2

In this section we describe the extremal cover of degree two. We describe only those aspects of covering theory needed to state the theorem, saving the general definitions and explanations for section 3.

A cover of degree two of a graph G is a graph H with a graph homomorphism ϕ: H → G such that each vertex and edge of H has exactly two preimages under ϕ, and for every edge e = (u, w) ∈ E(H) we have e^{∨} = (u^{∨}, v^{∨}), where ^{∨} denotes the other preimage. Equivalently, a degree two cover of G is a function ψ: E → Z/2Z; H is reconstructed as V (H) = V (G) × Z/2Z, and E(H) consisting of edges from (u, i) to (v, i + ψ(u, v)), ranging over all i ∈ Z/2Z and pairs (u, v) ∈ E(G).

Up to isomorphism (see section 3) there are 2^{|E|−|V |+1} degree two covers of a connected graph, G = (V, E). These isomorphism classes can be identified with classes of functions, ψ: E → Z/2Z, where we identify ψ_{1} with ψ_{2} if there is a function χ: V → Z/2Z such that ψ_{1}(e) − ψ_{2}(e) = χ(v) − χ(u) for all edges e = (u, v).

Any eigenfunction, f, of the adjacency matrix of G, viewed as a function on V (G), lifts to an eigenfuction of that of H, which we call an old eigenfunction. Those eigenfunctions of H which are orthogonal to the old eigenfunctions are called the new eigenfunctions, and their corresponding eigenvalues are called new eigenvalues. It is easy to see that the old eigenfunctions span the space of even functions on H (i.e. on V (H)), i.e. those satisfying f(v) = f(v^{∨}), and that the new eigenfunctions span that of the odd functions, i.e. those with f(v) = −f(v^{∨}).

By the Boolean n-cube, B^{n}, we mean the graph whose vertices are {0, 1}^{n}, two vertices being adjacent iff they differ in exactly one coordinate.

For example, B^{2} is just a cycle of length four. It has two covers of degree two, one being two disconnected copies of B^{2}, the other being a cycle of length eight. The old eigenvalues in both cases are 2, 0, −2 (0 with multiplicity two), and the new eigenvalues are 2, 0, −2 in the former case, and ±\sqrt{2} in the latter (each with multiplicity two).

Theorem 2.1 For any n (≥ 1) there is precisely one degree two cover (up to isomorphism) of the B^{n} with all new eigenvalues being ±\sqrt{n}; it is the unique cover containing no cycles of length four. All other covers have at least one new eigenvalue of absolute value > \sqrt{n}.

Proof The second sentence follows immediately from the first by considering the trace of the fourth power of the adjacency matrix. So it remains to prove the first, and by inspection we may assume n ≥ 3.

To prove the first, let V_{i} denote the family of subcubes of B^{n} of dimension i (e.g. V_{0} is the set of vertices, V_{2} can be identified with the set of cycles of length four, etc.). We say that a function f: V_{i} → Z/2Z is a cocycle for V_{i} if for each i + 1 dimensional subcube, H, the sum of f’s values on the i dimensional subcubes of H is zero. An easy topological argument gives:

Lemma 2.2 For n ≥ 2, the set of degree two covers of B^{n} up to isomorphism is in 1–1 correspondence with the set of cocycles for V_{2}; in this correspondence a point in the cover returns to itself by following a cycle of length four in the base graph, B^{n}, iff the cocyle has value 0 on that cycle.

Given this lemma it is easy to complete the proof. For clearly the function which is identically 1 on V_{2} is a cocycle, giving rise to a cover, ϕ: A^{n} → B^{n}, with no cycles of length four. Any other cover comes from a different V_{2} cocyle, which therefore has at least one cycle of length four. So it remains to prove that A^{n} has all new eigenvalues = ±\sqrt{n}. But notice that for any odd function, f, the sum of all values of f at vertices of distance two from a fixed vertex, v, is zero, since those vertices come in pairs, w, w^{∨}. Hence if M is the adjacency matrix of A^{n}, and f is any odd function, then M^{2}f = nf, which means that all new eigenvalues are either ±\sqrt{n}.

To prove the lemma, we may assume n ≥ 2. Let F(V_{i}) denote the set of all functions from V_{i} to Z/2Z. We get a complex (i.e. δ_{i+1} ∘ δ_{i} = 0) of vector spaces:

F(V_{0}) →^{δ_{0}} F(V_{1}) →^{δ_{1}} F(V_{2}) →^{δ_{2}} ⋯,  (2.1)

where δ_{i}(f) for a function f ∈ F(V_{i}) is the function on F(V_{i+1}) whose value at a subcube of dimension i+1 is obtained by summing f over all its subcubes of dimension i. By the above we know that set isomorphism classes of degree two covers is just F(V_{1})/im(δ_{0}); furthermore the V_{2} cocylces are just ker(δ_{2}). It is easy to see that δ_{1} yields an isomorphism between the two provided that the above sequence is exact at F(V_{1}) and F(V_{2}), i.e. im(δ_{i}) = ker(δ_{i+1}) for i = 1, 2.

To verify the exactness, view the vertices of B^{n} as {0, 1}^{n} sitting inside of R^{n}, and associate with each i-dimensional subcube the convex hull of its vertices. This realizes the unit n-cube, [0, 1]^{n}, as a CW-complex with each cell embedded isomorphically. This latter part implies that if X_{p} denotes the p-skeleton of the complex, then H^{i}(X_{p}, X_{p−1}) vanishes for i ≠ p, and is canonically isomorphic to F(V_{p}) for i = p. It follows that (see [Mun84]) the cohomology of [0, 1]^{n} is computed as the cohomology groups of the complex in equation 2.1, and therefore this complex is exact at i = 1, 2 (in fact it is exact at everywhere except i = 0, where ker(δ_{0}) consists of the constant functions, since [0, 1]^{n} is acyclic).

□

We conclude this section with some remarks about this extremal cover ϕ: A^{n} → B^{n}. We remark that we can actually construct a basis for the eigenspaces. For any

vertex v, let f_{+}^{v} be the function which is = n on v, = −n on v^{∨}, = \sqrt{n} on vertices of distance one to v, = −\sqrt{n} on those of distance one to v^{∨}, and 0 elsewhere. Define f_{−}^{v} similarly with \sqrt{n} replaced by −\sqrt{n}. It is easy to see that f_{±}^{v} are eigenfunctions with eigenvalues ±\sqrt{n}. Furthermore, any odd function f which is orthogonal to both f_{±}^{v} for some v must have f(v) = 0 (since it is both + and − the sum of the values of v’s neighbors times \sqrt{n}); hence an odd function orthogonal to all f_{±}^{v} must vanish identically, and so the f_{±}^{v}’s span the space of all odd function. So f_{±}^{v} with v ranging over one element of each vertex fiber of B^{n} yields a basis.

Secondly, we remark that A^{n} is a Cayley graph, and the underlying group’s representations can be easily described. A moment’s reflection shows that A^{n} is a Cayley graph on

G = {x_{1}, …, x_{n}, e | x_{i}^{2} = e^{2} = 1, [e, x_{i}] = 1, [x_{i}, x_{j}] = e}

with respect to the generators x_{1}, …, x_{n}, e. We claim that G has 2^{n} one-dimensional representations, and one other if n is even (of dimension 2^{n/2}) or two others, each of dimension 2^{(n−1)/2}, if n is odd. First note that G modulo the normal subgroup {1, e} is just (Z/2Z)^{n}, from which we get 2^{n} distinct characters. For n even G has 2^{n} + 1 conjugacy classes, {1}, {e}, and all classes {v, ve} with v ≠ 1, e. So there is just one more irriducible representation. Furthermore, any non-trivial character χ on the subgroup generated by e, x_{1}x_{2}, x_{3}x_{4}, …, x_{n−1}x_{n} (which is abelian of order 2^{1+(n/2)}) induces a representation, χ′ on G, and a calculation based on Frobenius reciprocity shows that χ′ is of norm 1, i.e. χ′ is the irreducible representation of dimension 2^{n/2}.

For n odd G has 2^{n} + 2 conjugacy classes, since u = x_{1} … x_{n} is now in the center, and the two irreducible representations are respectively of the form χ′ induced from χ being taken to be any non-trivial character on the subgroup generated by e, x_{1}, x_{2}x_{3}, x_{4}x_{5}, …, x_{n−1}x_{n} (abelian of order 2^{2+(n−1)/2}) with, respectively, χ(u) = ±1.

In particular, G is very similar to (but is not isomorphic) a standard 2^{n} order subgroup of the a standard Clifford algebra (generated by e_{1}, …, e_{n} with e_{i}^{2} = −1 and [e_{i}, e_{j}] = −1 for i ≠ j), in that both are cyclic extensions of (Z/2Z)^{n} and both have a very similar representation theory.

It is this representation theory that generalizes the Fourier analysis of B^{n}, and one might try to better understand this Fourier anaylsis by considering the analogous properties or liftings of properties to this (and other) cover(s).

3 Some relative notions in graph theory

In the previous section we described a cover of the boolean cube with small new eigenvalues. This cover is also the only one such that all non-backtracking walks of length two are distinct, and in fact any two vertices v, w in the cover can be joined by a path of legth two if ϕ(v), ϕ(w) are of distance two in the base graph. These types of properties seem to indicate that our cover is a good expander relative to that fact that it covers the Boolean cube (which is not very good expander itself, relative to most graphs of the same degree and number of vertices).

In this section we make precise relative notions of expansion, and prove theorems relating such notions to the new eigenvalues and new spectral radius. We explain how they generalize the standard notions of expansion and small second eigenvalues.

3.1 Review of Covering and Galois Theory

Recall that a homomorphism ϕ: H → G of graphs is a covering if ϕ is locally an isomorphism; the simplest way to make this precise is to view graphs as topological spaces, and then our notion of cover is the standard topological one (see [Fri93]); there are numerous combinatorial definitions (see [Big74, CDS79]) which work as well, although they are slightly more complicated when the graphs have self-loops or multiple edges. Any of these notions should suffice for what follows. These definitions work both for directed and undirected graphs (in the directed case edges must map to edges in a way which preserves their orientation).

For example, to give a mapping of graphs (respectively, directed graphs) H → B_{d} is to color the edges of H with d colors; the map is a covering precisely if it is a proper coloring, i.e. when each vertex is incident upon exactly one edge of each color (respectively, exactly one incoming and one outgoing edge of each color). (Recall from section 1 that B_{d} is the graph on one vertex with d half-loops in the directed case, and d self-loops in the undirected case.)

Returning to a covering ϕ: H → G, by a fiber of ϕ we mean the inverse image of a vertex or an edge of G in H. If G is connected, the cardinality of a fiber is constant, and is called the degree. The base graph of the cover is G, and the covering graph is H. Sometimes we simply refer to H as cover, understanding a map ϕ: H → G.

Recall that a graph over G is a pair (H, ϕ) of a graph H and a graph homomorphism ϕ: H → G. A morphism of two graphs over G, from (H, ϕ) to (H′, ϕ′) is a map ψ: H → H′ such that ϕ′ ∘ ψ = ϕ. An automorphism of a graph over G is a morphism to itself with an inverse.

Recall (see [Fri93]) that a covering ϕ: H → G of degree d is called Galois if H has d distinct automorphisms over G. Denoting the Galois group by G = Aut_{G}(H) and fixing one vertex of H in each fiber (i.e. giving a section of ϕ, ψ: V (G) → V (H)), we can identify H’s vertices with V (G) × G (namely by identifying gψ(v) with (v, g) for all v ∈ V (G) and g ∈ G); this in turn determines for each (triple e, u, v with) e = {u, v} ∈ E(G) an element, ϕ = ϕ(e, u, v) ∈ G as the unique element such that a lift of e maps (v, 0) to (v, ϕ).

Conversely, given any graph, G, a group G, and for each e = {u, v} ∈ E(G) an element ϕ(e, u, v) ∈ G such that ϕ(e, u, v) = −ϕ(e, v, u), this data determines a Galois cover H by reversing the above construction, i.e. V (H) = V (G) × G and (u, i) is connected to (v, i + ϕ(e, u, v)) for each e = {u, v} ∈ E(G) and i ∈ G.

We claim that ϕ and ϕ′ determine isomorphic covers iff there is a function τ: V (G) → G such that for all e = {u, v} ∈ E(G) we have

ϕ(e, u, v) − ϕ′(e, u, v) = τ(v) − τ(u).

This can be checked directly; alternatively, this follows from the fact that the set of Galois covers is isomorphic to Hom(π_{1}(G), G), which is isomorphic to H^{1}(G, G), which is equivalent to the set of ϕ’s modulo the above equivalence relation.

The connection between Galois theory and covering theory is that every covering, H, of G has a covering, K, of H such that K is Galois over G (and therefore over H) (and, of course, every Galois covering is a covering).

We also remark that like in most Galois theories, every covering of graphs or directed graphs of degree two is necessarily Galois; namely, if H is a degree two cover of G and for each vertex v ∈ V (H) and e ∈ E(H) we let v^{∨}, e^{∨} denote the other element of the fiber of v, e, then ^{∨} is an automorphism.

3.2 Eigenvalue Theory

Given a covering ϕ: H → G, any eigenvector, v, of the adjacency matrix of A_{G} of G, viewed as a function on the vertices of G, lifts via ϕ to a function on H, which is an eigenvector of A_{H} since ϕ is a covering. We call such an eigenvector an old eigenvector. Any eigenvector of H which is orthogonal to all the old eigenvectors will be called a new eigenvector. The old eigenvectors clearly span the space of functions on the vertices of H which are liftings from functions on G, i.e. are constant on ϕ’s fibers; we refer to such functions as old functions. Similarly the new eigenvectors clearly span the space of functions whose sum on each ϕ’s fibers is zero, which we will call new functions. We define the new spectral radius to be the largest absolute value of an eigenvalue corresponding to a new eigenfunction.

By Hall’s theorem, any directed d-regular graph has a covering map to B_{d}, the directed graph with one vertex and d edges (which are self-loops). The new spectral radius in this case is just the “second eigenvalue,” i.e. the absolute value of the second largest eigenvalue in absolute value (we use quotation marks to indicate that we take the absolute value). Hence the new spectral radius is a generalization of the “second eigenvalue” which appears so frequently in graph theory.

It is easy to see that given a Galois covering, H, of G with Galois group G, we can calculate the eigenvalues of H in terms of functions on G, from the knowledge of ϕ as above, if we know the representations of G. This is probably simplest and is most efficient when G is a cyclic group.

Proposition 3.1 Let G, H, ϕ, G be as above with G abelian. For each character, χ, of G let A_{χ} be the square matrix indexed on V (G) such that the (u, v)-th entry is the sum of all χ(ϕ(e, u, v))’s (if G is not a multigraph then there are zero or one terms in this sum). Then the eigenvalues of H are simply the eigenvalues of A_{χ} ranging over all χ’s. Furthermore, if G is not abelian, then for each irreducible representation χ of dimension d let A_{χ} be the d|V | square matrix which is a |V | × |V | square block matrix whose (u, v) block is the sum of all χ(ϕ(e, u, v))’s. Then each eigenvalue of A_{χ} occurs as an eigenvalue of multiplicity d in H.

The proof is easy and is just the same as in the case of Cayley graphs. Of course, the eigenvectors of H can be read off from those of A_{χ} in the obvious way.

We point out that the above proposition leads to a much more efficient method for calculating the new eigenpairs than simply computing the eigenvalues of the adjacency matrix of H. This was used in generating the data in section 5.

We finish by noting that degree two covers are related to the notion of signed graphs (as in [Har54, Zas81, Kau89, CV90]). A signed graph is just a graph, G, with a map ϕ: E(G) → {+, −}. Its eigenvalues are defined to be the eigenvalues of its adjacency matrix whose nonzero entries are ±1 according to ϕ. By the above, these eigenvalues are just the new eigenvalues of the degree two cover of G associated to ϕ, by identifying {+, −} with Z/2Z. As an example, our theorem 1.1 says that there is precisely one signed graph up to isomorphism whose underlying graph is the boolean cube and with all eigenvalues ±\sqrt{n}.

3.3 Relative and Absolute Notions

Here we review what is meant by a relative and an absolute notion. In brief, an absolute notion is some notion defined on graphs or some subfamily of graphs, and a relative notion is one which is defined for all or some subfamily of maps ϕ: H → G. We explain the relationship between them by an example.

The notion of new spectral radius was defined for any covering map ϕ: H → G. Now consider the family of d-regular directed graphs, G_{d}. Recall B_{d} is the graph with one vertex and d self-loops. B_{d} is a terminal object for G_{d} in the sense that (by Hall’s theorem) any H ∈ G_{d} admits a covering map ϕ: H → B_{d}. Of course, this map is not in general unique, but the new spectral radius of the covering map is independent of the map, and is simply the “second eigenvalue.” We say that the new spectral radius is a relative version of the “second eigenvalue.”

Another example, again with respect to covering maps (in the relative situation) and G_{d} (in the absolute situation), is furnished by Galois covers. The Galois cover is a relative version of the notion of a directed Cayley graph, for to give a Galois cover ϕ: H → B_{d} is the same thing as giving H the structure of a Cayley graph.

More examples of relative notions will be given later in this section when we describe relative notions of expansion.

Our discussion is rather loose, for usually one requires a unique mapping in the definition of terminal objects. We also mention that d-regular undirected graphs do not admit a terminal object, even in the loose sense used above, unless one passes to a larger category such as that of pregraphs (see [Fri93]). We explain more about this in section 4.

3.4 Relative Expansion

In this subsection we describe the relation between relative edge and vertex expansion and the new spectral radius, an analogue of the well known relation between the eigenvalues of regular graphs and expansion. Recall that the Laplacian of a graph is Δ = D − A, where A is the adjacency matrix and D is the diagonal matrix whose entries are the degrees of the vertices. In particular, if G is d-regular, then eigenpairs (f, λ) of A give rise to eigenpairs (f, d − λ) of Δ and vice versa. For any covering map, Laplacian eigenpairs on the base graph lift to eigenpairs on the covering graph, just as do adjacency matrix eigenpairs.

If G is a d-regular graph such that the non-trivial spectral radius of the adjecency matrix of G is small, then G has various nice properties including good expansion properties. This fact is straightforward and was observed by a number of people independently (explicitly appearing in [AM85, Buc86, Tan84], probably implicitly much earlier). The same is true in the relative situation. Determining the optimal amount of expansion for a given size of spectral radius is more difficult (see [Kah92]). Here we give the simplest type of relative expansion bounds:

Theorem 3.2 Let ϕ: H → G be a cover of degree n with new spectral radius ρ. Let u, v ∈ V (G) such that there are d edges from u to v in G. Then for any A ⊂ ϕ^{−1}(u) and B ⊂ ϕ^{−1}(v), if e(A, B) denotes the number of edges in H from A to B and a = |A|, b = |B|, we have

|e(A, B) − abd/n| ≤ ρ\sqrt{a(n − a)b(n − b)} /n.

The property that subsets A, B of appropriate size have many edges between them, as implied above, is typically called edge expansion, and the above implies the relative version of it. A special case of the above implies the graph has good relative vertex expansion:

Corollary 3.3 Let ϕ: H → G be a cover of degree n with new spectral radius ρ. Let u, v ∈ V (G) such that there are d edges from u to v in G. Then for any A ⊂ ϕ^{−1}(u) and B ⊂ ϕ^{−1}(v) which have no edges between them, we have:

(n/|A| − 1)(n/|B| − 1) ≥ d^{2}/ρ^{2}.

In other words, for any subset A ⊂ ϕ^{−1}(u) we have Γ(A) ∩ ϕ^{−1}(v) is of size at least:

\frac{n}{1 + (n/a − 1)ρ^{2}/d^{2}}

Proof (Of the theorem.) Let P_{new}, P_{old} denote the projections onto the new and old spaces. If M is the adjacency matrix of H we have

e(A, B) = (Mχ_{A}, χ_{B}) = (MP_{new}(χ_{A}), P_{new}(χ_{B})) + (MP_{old}(χ_{A}), P_{old}(χ_{B}))

It is easy to see calculate that the latter summand on the left-hand-side is just abd/n. On the other hand the former summand can be bounded by the facts that

|P_{new}(χ_{A})| = \sqrt{a(n − a)/n}, |P_{new}(χ_{B})| = \sqrt{b(n − b)/n}, ∥M|_{new}∥ = ρ,

which imply the theorem.

□

The same proof yields the following messier but more useful theorem for what is to come:

Theorem 3.4 Let ϕ: H → G be a cover of degree n with new spectral radius ρ. Let V (G) = {v_{1}, …, v_{r}}, let d_{ij} be the number of edges from i to j, and let A, B ⊂ V (H) with a_{i} = |A ∩ ϕ^{−1}(v_{i})| and b_{i} = |B ∩ ϕ^{−1}(v_{i})|. Then

|e(A, B) − ∑_{i,j} a_{i}b_{j}d_{ij}/n| ≤ ρ\sqrt{∑_{i,j} a_{i}(n − a_{i})b_{j}(n − b_{j})} / n.  (3.1)

In particular we have

e(A, \overline{A}) = (∑ a_{i}d_{ij}) − ρ(∑ a_{i}) + (ρ(∑ a_{i}^{2}) − ∑ a_{i}a_{j}d_{ij})/n,

where \overline{A} denotes the complement of A in V (H).

Let us call a cover a (relative) ρ-edge expander if it satisfies equation 3.1. We claim that if a cover is an edge expander this gives an upper bound on the largest new eigenvalue, or equivalently a lower bound on the smallest new eigenvalue of the Laplacian, at least assuming the base graph is an expander.

Theorem 3.5 Let ϕ: H → G be a cover with G a d-regular graph with new spectral radius η. If H is a relative ρ-edge expander, then any new eigenvalue of the Laplacian is at least

(d − max(ρ, η))^{2}/8.

Proof This theorem is an analogue of Cheeger’s inequality, and we will use Cheeger’s inequality for graphs as a lemma:

Lemma 3.6 Let f be an eigenfunction of the Laplancian of a graph, with eigenvalue λ, and let S ⊂ V be the set on which it takes positive values. Then h(S) ≤ 2\sqrt{λ}, where

h(S) ≡ max_{T ⊂S} |∂T |/|T |, where ∂T = E(T, \overline{T}).

This is (essentially) proven in [JS89]. We remark that the above is true with S replaced by any “nodal region” of f, and that many other theorems in analysis immediately imply graph theoretic analogues when eigenfunctions in graph theory are interpreted in a certain way (see [Fri93]). Such an interpretation is implicit in Dodziuk’s paper, [Dod84], with which he converts Cheeger’s inequality into the inequality h ≤ 2\sqrt{dλ} for graphs, where d is the maximum degree; the advantage of his proof is that it is very simple and elegant, the disadvantage is that a factor of d arises since the Raleigh quotient for graphs involves two different measures whose “ratio,” in a certain sense, is d. A different analysis is required to obtain an inequality independent of d, as was first done by Alon in [Alo86] (independently of Dodziuk’s work), and improved upon (by a different method) in [JS89] (see also [MW88]).

Before embarking on the proof, let us remark on the difference between the absolute and relative case. With the hypotheses of the theorem we have

e(A, \overline{A}) ≥ (d − ρ)(∑ a_{i}) + (ρ(∑ a_{i}^{2}) − ∑ a_{i}a_{j}d_{ij})/n,

which by Cauchy-Schwartz is

≥ (d − ρ)|A|(1 − (∑ a_{i}^{2})/(n ∑ a_{i})).  (3.2)

The problem is that if all a_{i}’s are roughly 0 or n, this won’t give a good lower bound for h needed to apply the above lemma. In the absolute case one has only one a_{i}, which can be assumed to be ≤ n/2, since a non-trivial eigenfunction has either ≤ n/2 positive values or ≤ n/2 negative values.

The proof of the above theorem follows from the above lemma along with the following:

Lemma 3.7 Let G be a d-regular graph with new spectral radius η(G), and let ϕ: H → G satisfy equation 3.1. Then for any P with |P | ≤ |V (H)|/2 we have

h(P) ≥ (d − max(ρ, η))/2.

Proof Let A ⊂ P, and let a_{i} be as in equation 3.1. Letting θ ≤ 1 satisfy ∑ a_{i}^{2} = θn ∑ a_{i}, we have

e(A, \overline{A}) ≥ (d − ρ)|A|(1 − θ),

by equation 3.2. Now the vector a⃗ = (a_{1}, …, a_{r}) on the vertices of G, and write

a⃗ = nα1 + v,

with v orthogonal to 1. We have α ≤ 1/2 by assumption on P, and clearly ∑ a_{i} = nαr. Now

|v|^{2} = |a⃗|^{2} − n^{2}α^{2}|1|^{2} = ∑ a_{i}^{2} − n^{2}α^{2}r,

while if D_{G} denotes the adjacency matrix of G we have

∑ a_{i}a_{j}d_{ij} = (D_{G}a⃗, a⃗) ≤ d|nα1|^{2}+η|v|^{2} = dn^{2}α^{2}r+η(∑ a_{i}^{2}−n^{2}α^{2}r) = n|A|((d−η)α+ηθ).

Hence

e(A, \overline{A}) ≥ (d − ρ)|A| + |A|((ρ − η)θ − α(d − η)),

and along with the first inequality for e(A, \overline{A}) this yields the lemma.

□

One could ask to what extent one can relax the condition on the base graph, G, in theorem 3.5. Clearly one can prove a (much less pleasant to state) theorem for general G under some type of edge expansion condition (which is all that is really being used above). On the other hand, one clearly needs some type of restriction on G to have a reasonable theorem. For consider G being a cycle of length n, and H a cycle of length mn. Then H is as good an expander as one could hope for relative to being a cover of G; indeed, non-backtracking walks from a fixed point in H of any length cover as many different vertices and edges as is possible. Yet the new eigenvalues of H’s Laplacian are as small as 2 − 2 cos(2π/(nm)) which is roughly proportional to (mn)^{−2}.

4 Spectral Theory of Pregraphs

One can hardly have a complete discussion of relative notions for covering maps without discussing how such notions carry over to pregraphs (see appendix A and [Fri93]). The main task is to describe the spectral theory for pregraphs, which we do first. The other notions are easy to carry over.

We claim that our hand is forced in defining spectral notions for pregraphs, assuming we want to maintain consistency with covering theory for graphs. First, let us recall the relevant notions for graphs. For a graph, G, we have L_{G}^{2}(dV), the space of real valued functions on V (G) with its natural inner product. We have the adjacency matrix of G, A_{G}, which can be viewed as a matrix of integers or as an operator on L^{2}(dV). Its eigenpairs (eigenvalues and eigenvectors) are what we typically call the eigenpairs of G. Sometimes we also define the Laplacian of G, Δ_{G}, and work with its eigenpairs.

Now consider a covering map ϕ: H → G of graphs of degree d. We claim that all the above spectral notions on G can be defined in terms of H’s spectral theory restricted to the old functions. For example, for f, g ∈ L_{G}^{2}(dV) we have

(f, g)_{L_{G}^{2}(dV)} = (ϕ^{∗}f, ϕ^{∗}g)_{L_{H}^{2}(dV)}/d,

and

A_{G}f = ϕ_{∗}A_{H}ϕ^{∗}f,

where (ϕ^{∗}f = f ∘ ϕ and) ϕ_{∗}: F → L_{G}^{2}(dV) is the inverse of ϕ^{∗}.

The above functoriality of spectral notions forces our hand in defining spectral notions for pregraphs. For a graph, G, we denote its naturally associated pregraph by G̃.

Definition 4.1 A connected pregraph, B, is realizable if there is a finite graph G with a covering map of pregraphs ϕ: G̃ → B.

Given a realizable pregraph, B, take any such G, ϕ and define L_{B}^{2}(dV) to be real valued functions on V (B) with the inner product

(f, g)_{L_{B}^{2}(dV)} = (ϕ^{∗}f, ϕ^{∗}g)_{L_{G}^{2}(dV)}/d,

where d is the degree of the cover; also define A_{B}f = ϕ_{∗}A_{G}ϕ^{∗}f. It is easy to see that these notions are independent of the covering G, ϕ. More explicitly, if δ_{u} for u ∈ V (B) denotes the characteristic function of u, we have

A_{B}δ_{u} = ∑_{e={u,v}∈E_{u}} δ_{v} = ∑_{v}(A_{B})_{u,v}δ_{v},

i.e. A_{B} on basis {δ_{v}}_{v∈V (B)} is represented by the matrix whose (u, v)-th entry is the number of v joining edges in E_{u}. This matrix is not symmetric in the sense that (A_{B})_{u,v} is not generally equal to (A_{B})_{v,u}, but the operator A_{B} is symmetric with respect to the L_{B}^{2}(dV) inner product, i.e. (A_{B}f, g) = (f, A_{B}g).

For example, for B_{2,3} (see appendix A) with u the vertex of degree 2, we have (A_{B})_{u,v} = 2, (A_{B})_{v,u} = 3, but

(aδ_{u} + bδ_{v}, cδ_{u} + dδ_{v}) = 3ac + 2bd,

so that (A_{B}f, g) = (f, A_{B}g).

It is now clear that we can define eigenpairs of pregraphs in a natural and functorial way, and speak of old and new eigenpairs in the context of pregraphs. We also remark that the measure dE = dE(G) (see appendix B) from graph theory carries over to pregraphs in the same way that dV does, and the Rayleigh quotient (see appendix B), nodal regions, and similar notions (as in [Fri93]) carry over as well.

Finally we describe the spectral theory for directed pregraphs. The same realizability definition and spectral notions defined via a cover go through. In this case we have two adjacency matrices, A_{B}^{forw}, A_{B}^{back} of a pregraph, B, with

(A_{B}^{forw})_{u,v} = ∑_{e=(u,v)∈E_{u}} 1, (A_{B}^{back})_{u,v} = ∑_{e=(v,u)∈E_{u}} 1.

Again, unlike the theory of directed graphs, (A_{B}^{forw})_{u,v} is not in general = (A_{B}^{back})_{v,u}, but the operators are transposes of one another in the sense that,

(A_{B}^{forw}f, g) = (f, A_{B}^{back}g)

with respect to the L_{B}^{2}(dV) inner product.

From here it is easy to see that all notions defined for and theorems proven about graph coverings in section 3 also hold for graphs, G, and coverings ϕ: G̃ → B. Also, nodal regions (see appendix B) can be defined for pregraph eigenfunctions, and comparison and restriction theorems as in [Fri93] hold in this setting.

We finish with a pedantic remark about graphs and pregraphs. There is a way to correct that fact that there do not exist terminal objects in these covering theories. Namely, we can define a new category, say quasipregraphs, whose objects are pregraphs, and whose morphism are pregraph morphism modulo ϕ ∼ ϕ′ if ϕ, ϕ′ ∈ Hom(H, G) and there are vertex preserving pregraph automorphisms α, β of H, G respectively such that ϕ′ = β ∘ ϕ ∘ α. Spectral notions are independent of such α, β and thus carry over to this category; furthermore, all morphisms to minimal pregraphs are easily seen to be unique, so a terminal objects exist for the set of objects with a given universal cover. Perhaps this is the most natural context in which to study eigenvalue theory.

5 Numerical Computations for B^{3}

In this section we present some numerical results on the new eigenvalues of cyclic covers of B^{3}. We order the new eigenvalues in decreasing order and sort them lexicographically, i.e. the first graph appearing in the table is the one whose largest new eigenvalue is as small as possible. The negative eigenvalues are omitted, being redundant (since the base graph is bipartite).

In table 1 we list the new eigenvalues of all 32 degree two covers of B^{3}, listing first the eigenvalues and then the number of times (out of 32) such data occurs. This data shows that there are covers with some new eigenvalues of absolute value < \sqrt{3}; hence it is not true that the i-th largest eigenvalue of our distinguished cover no greater than the i-th largest eigenvalue of any other cover (except for i = 1).

In table 2 we list the new eigenvalues of all 243 degree three covers of B^{3}; we only list every other new eigenvalue, since they each occur with even multiplicity (which is New Eigenvalues

Times

1.732, 1.732, 1.732, 1.732  1
2.236, 2.236, 1, 1  3
2.414, 1.732, 1.732, .414  12
2.414, 2.414, .414, .414  3
2.709, 1.903, 1, .193  12
3, 1, 1, 1  1

Table 1: The new spectra of degree two covers of B^{3}.

clearly true of the new spectrum of any cyclic cover of odd degree). We see that there are two covers with optimal eigenvalues; they can be described as follows.

Consider [0, 1]^{3} with its standard orientation, and its six bounding faces with the outward normal orientation (i.e. “right-hand-rule” with thumb pointing outward), F_{1}, …, F_{6}, which are, respectively, front, back, left, right, top, and bottom faces. To give a cyclic cover of degree n is the same as giving a tuple (s_{1}, …, s_{6}) with s_{i} ∈ Z/nZ such that s_{1} + ⋯ + s_{6} = 0 (to which we associate the cover such that traversing F_{i} in its outward normal orientation results in adding s_{i}).

The two optimal cyclic covers of degree three of B^{3} are those with s_{1} = ⋯ = s_{6} = ±1.

In table 3 we list for various values of d the three best spectral of cyclic covers of degree d, along with the s_{i} values and the number of times equivalent s_{i} values occur. We say two tuples (s_{1}, ⋯, s_{6}) are equivalent if they differ by a symmetry of the cube (i.e. via rigid motion, of which there are 24) or by multiplication by a multiplicative unit in Z/nZ. New tuples (s_{1}, ⋯, s_{6}) obtained by cube symmetries are not isomorphic as covers of B^{3}, since the map to the base graph changes under such a symmetry, but they are isomorphic graphs. Also, in this table we indicate the multiplicity, n, of an eigenvalue by appending ×n to the entry.

There seems to be no simple pattern for the best cover, other than d = 2, 3 where the s_{1} = ⋯ = s_{6} = 1 is optimal. We also remark that what seems like a natural choice for an optimal cover with d = 6, namely s_{1} = ⋯ = s_{6} = 1, has new eigenvalues

2.449 × 4, 2 × 6, 1.732 × 4, 0 × 6,

and hence, by table 3, is not nearly optimal. We mention that there are two other degree eight covers with new spectral radius 2.414, namely 265577(24) and 334473(48). We also call the reader’s attention to the interesting optimal covers of degree 7 and 9, where the three pairs of opposite faces have s_{i} values which range over the three pairs of Z/nZ multiplicative units whose sum is n (n = 7, 9).

As a final comment regarding the numerical data, the optimal cover of degree four New Eigenvalues

Times

2., 2., 2., 0  2
2.30278, 2., 1.30278, 1.  8
2.30278, 2.1889, 1.30278, 0.45685  12
2.39417, 1.73205, 1.50597, 1.  12
2.42357, 2., 1.36024, 0.525398  48
2.51414, 2.08613, 1., 0.571993  12
2.55761, 2.1889, 0.677214, 0.45685  24
2.57667, 1.90507, 1.28699, 0.274169  48
2.63372, 1.63372, 1.47325, 0.473255  24
2.64575, 1.73205, 1., 1.  6
2.64575, 2., 1., 0  16
2.73205, 2., 0.732051, 0  6
2.80588, 1.73205, 1., 0.356394  24
3., 1., 1., 1.  1

Table 2: The new spectra of cyclic degree three covers of B^{3}.

occurs in two non-equivalent ways. This is an example of non-equivalent covers of B^{3} with the same eigenvalues.

The number of covers of B^{4} seems prohibitively large for a short computation. We describe why it seems unlikely to have as simple answers. The problem is that there is no obvious orientation on the two dimensional faces. The fact that each edge is incident on three faces is one possible reason for this. A similar remark holds for B^{n} with n ≥ 4.

A Review of Pregraphs

Here we review the relevant notions of pregraphs and explain their use. Graphs with the same universal cover, T, often have similar or related properties. For example, to say that a directed graph is d-regular equivalent to saying that it admits a covering map to B_{d}, which is equivalent to saying that its universal cover is the infinite d-regular tree, T_{d}. There are several advantages to the description in terms of being a cover of B_{d}; for one this seems simpler, in that B_{d} is a finite graph, and for another relative notions such as the new spectra and expansion arise from the covering map to B_{d}, not the covering from T_{d}.

Unfortunately, for most types of graphs and trees, T, there is no object B such that every graph with universal cover T has a covering map to B. Consider the set of graphs with all vertices of degree two or three, and with all degree two vertices adjacent only to degree three vertices, and with all degree three vertices adjacent only to degree two vertices. We denote this family G_{2,3}. All such graphs have the same universal cover, the tree T_{2,3}, but there is no object B to which all have a covering map.

What is clear is that there is a small amount of data needed to describe graphs in G_{2,3}. There are two types of vertices, say u, v, each u vertex having two edges to a v type vertex, and each v type vertex having three edges to u type edges (and no other edges). This data is known as a pregraph (see [Fri93]). The formal definition is as follows:

Definition A.1 A directed pregraph is a graph G = (V, E) with a partition of E as the union of sets

E = ∐_{v∈V} E_{v}^{to} ⨿ E_{v}^{from},

with all E_{v}^{to} edges of the form (x, v) for some x ∈ V and all E_{v}^{from} edges of the form (v, x). A pregraph (i.e. undirected pregraph) is a directed pregraph with a vertex fixing edge-orientation reversing involution, or simply a graph with a partition of its edges as the union of sets E_{v} with each E_{v} edge having at least one endpoint being v.

Given a pregraph, a globalizing pairing is a pairing of its edges such that e ∈ E_{v} is paired with e′ ∈ E_{v′} implies that both e′ and e’s endpoints are v, v′; this data determines a graph. Conversely, any graph, G, can be viewed as a pregraph, G̃ with each graph edge, e = {v, v′} giving rise to one E_{v} edge and one E_{v′} edge. Similarly for directed graphs. One can define morphisms, covering maps, etc. of pregraphs (see [Fri93]). In short, pregraphs (analogous to presheaves or preschemes) are generalizations of graphs, whose objects consist of the local (i.e. vertex local) data of what might be a graph.

Figure 1: Graphs covering B_{2,3}

For example, all graphs in G_{2,3} admit covers to the pregraph B_{2,3} depicted in figure 1; the figure depicts the map from the two G_{2,3} graphs with minimal number of vertices. (Formally, B_{2,3} has two vertices, u, v, with E_{u} containing two {u, v} edges and E_{v} containing three {u, v} edges.)

Given a connected graph, G, and a covering ϕ: G̃ → B of a pregraph, B, we define the degree of the cover to be |V (G)|/|V (G_{1})| where G_{1} is a graph with minimal number of vertices whose pregraph admits a map to B. This definition is not so canonical, but at least assures that we have [H̃: B] = [H: G][G̃: B] for coverings H of G, where [ : ] denotes the degree of the cover.

B The Rayleigh Quotient

Here we review some of the notions of [Fri93].

We identify a graph, G, with its geometric realization, which is the metric space with one point for each vertex and an interval of unit length joining two such points for each edge whose endpoints are the corresponding vertices (for directed graphs each edge also has an orientation). On G we have two natural measures, dV, which counts points, and dE which is Lebesgue measure on the edges viewed as intervals. For any continuous function f on the geometric realization with square integrable derivative along the edges, we define its Rayleigh quotient to be

R(f) = \frac{∫ |∇f|^{2} dE}{∫ f^{2} dV} .

Given a function f defined only on the vertices, we can extend it to a function, f̃, on the geometric realization by interpolating linearly along the edges; we call such functions edgewise linear. The successive minimizers of R (subject to orthogonality with respect to dV) are easily seen to be the edgewise linear functions whose restrictions to the vertices are just the classical Laplacian eigenfunctions. Defining the Rayleigh quotient on this wider class of functions enables many of the classical results on nodal regions and monotonicity (and Cheeger’s inequality, as first observed by Dodziuk) to carry over essentially verbatim to graph theory analogues (see [Fri93]).

References

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

[AM85] N. Alon and V.D. Milman. λ_{1}, isoperimetric inequalities for graphs and superconcentrators. J. Comb. Theory Ser. B, 38:73–88, 1985.

[Big74] Norman Biggs. Algebraic Graph Theory. Cambridge University Press, London, 1974.

[Buc86] Marshall W. Buck. Expanders and diffusers. SIAM J. Alg. Disc. Methods, 7:282–304, 1986.

[CDS79] D. Cvetkovic, M. Doob, and H. Sachs. Spectra of Graphs. Academic Press, New York, 1979.

[CFG^{+}85] B. Chor, J. Friedman, O. Goldreich, J. Håstad, S. Rudich, and R. Smolensky. The bit extraction problem or t-Resilient functions. In 26th Annual Symposium on Foundations of Computer Science, pages 396–407, 1985.

[CV90] P.D. Chawathe and G.R. Vijayakumar. A characterization of signed graphs represented by root system D_{∞}. Europ. J. Combinatorics, 11:523–533, 1990.

[Dod84] Jozef Dodziuk. Difference equations, isoperimetric inequality and transcience of certain random walks. Trans. AMS, 284:787–794, 1984.

[Fri92] Joel Friedman. On the bit extraction problem. 33rd FOCS, pages 314–319, 1992.

[Fri93] Joel Friedman. Some geometric aspects of graphs and their eigenfunctions. Duke J. Math, 69:487–525, 1993.

[Har54] Frank Harary. On the notion of balance of a signed graph. Michigan Math. J., 2:143–146, 1953–1954.

[JS89] Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comp., 18:1149–1178, 1989.

[Kah92] Nabil Kahale. On the second eigenvalue and linear expansion of regular graphs. 33rd FOCS, pages 296–303, 1992.

[Kau89] Louis H. Kauffman. A tutte polynomial for signed graphs. Discrete Appl. Math., 25:105–127, 1989.

[Mun84] James R. Munkrees. Elements of Algebraic Topology. Benjamin/Cummings, 1984.

[MW88] Bojan Mohar and Wolfgang Woess. A survey on spectra of infinite graphs. Universita Degli Studi di Milano (and Preprint Series, Dept. Math., Univ. E.K. Ljubljana), 23:281–316, 1988.

[Tan84] R.M. Tanner. Explicit concentrators from generalized n-gons. SIAM J. Alg. Disc. Methods, 5:287–293, 1984.

[Zas81] Thomas Zaslavsky. The geometry of root systems and signed graphs. Amer. Math. Monthly, 88:88–105, 1981. d

New Eigenvalues

s_{1} … s_{6} (times)
2 1.732 × 4 111111(1)
2.236 × 2, 1 × 2  111100(3)
2.414, 1.732 × 2, .414  110101(12)
3 2 × 6, 0 × 2 111111(2)
2.302 × 2, 2 × 2, 1.302 × 2, 1 × 2  121221(8)
2.302 × 2, 2.188 × 2, 1.302 × 2, .456 × 2  111102(12)
4 2.236 × 6, 1 × 6 112233(6), 223131(12)
2.414, (2.316, 2.030, 1.732, 1.579) × 2, 0.414, …  112121(24)
2.414 × 2, 2.101 × 4, 1.259 × 4, 0.414 × 2  222231(6)
5 (2.388, 2.263, 2.218, 2.098, 1.370, …) × 2 113343(48)
(2.428, 2.427, 2.032, 1.959, 1.453, …) × 2  142242(96)
(2.469, 2.277, 2.116, 2.107, 1.170, …) × 2  143241(48)
6 2.414 × 2, 2.288 × 4, 2. × 6, 0.874 × 4, … 222255(6)
(2.414, 2.302, 2.207, 2.188, 2.061, …) × 2  444435(12)
2.414 × 4, (2.394, 2.101, 1.732, 1.505, …) × 2  244455(24)
7 (2.391, 2.164, 1, 0.772) × 6 254361(48)
(2.440, 2.336, 2.307, 2.285, 2.173, …) × 2  223266(72)
(2.454, 2.424, 2.361, 2.213, 2.135, …) × 2  163362(144)
8 2.414 × 2, 2.334 × 4, 2.308 × 4, 2.146 × 4, …  264471(48)
2.414 × 2, 2.334 × 6, 2.236 × 2, 1.732 × 4, …  223377(12)
(2.414, 2.412, 2.338) × 2, 2.334 × 4, 2.093 × 2, …  446675(48)
9 2.429 × 6, 2.302 × 2, 2.223 × 6, 2 × 2, … 275481(48)
(2.463, 2.423, 2.402, 2.400, 2.217, …) × 2  225486(144)
(2.494, 2.453, 2.423, 2.296, 2.283, …) × 2  223281(144)

Table 3: The best new spectra of cyclic covers of B^{3}.