Some Geometric Aspects of Graphs and their Eigenfunctions

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

October 4, 1993

Abstract

We study three mathematical notions, that of nodal regions for eigenfunctions of the Laplacian, that of covering theory, and that of fiber products, in the context of graph theory and spectral theory for graphs. We formulate analogous notions and theorems for graphs and their eigenpairs. These techniques suggest new ways of studying problems related to spectral theory of graphs. We also perform some numerical experiments suggesting that the fiber product can yield graphs with small second eigenvalue.

1 Introduction

In analysis on manifolds there is an extensive literature on isoperimetric problems and the Laplacian. Some analogues in graph theory, usually concerning eigenvalues of the adjacency matrix or the associated “Laplacian,” are known (see [Alo86, CDS79, Dod84]). But on the whole much less in known for graphs, especially for isoperimetric type problems, and many tools from analysis are in want of a good generalization to graph theory.

In this paper we show that the concept of nodal regions in analysis has a precise analogue in graph theory. This gives us geometric insight into the eigenvectors. We show how this, along with information theory and graph coverings, can give some slight improvements to certain eigenvalue bounds. We also show that the mathematical concept of a fiber product gives an interesting type of graph product; it generates new d-regular graphs from old ones in a simple manner, and numerical experiments show that it can yield graphs with small second eigenvalue. In introducing the fiber product we discuss covering and Galois theory for graphs.

∗This paper was written while the author was on leave at the Hebrew Unversity, Dept. of CS. Computations were performed on both Hebrew and Princeton University facilities, including equipment purchased by a grant from DEC. The author also wishes to acknowledge the National Science Foundation for supporting this research in part under a PYI grant, CCR–8858788, and IBM for an IBM faculty development award.

In the process of discussing the fiber product we formulate some notions of covering theory and Galois theory for graphs; while such theories are more or less known, we give a precise and concise formulation describing most situations which arise.

In section 2 we notice that graph eigenvectors can be viewed as minimizers of a Rayleigh quotient over, say, piecewise differentiable functions on the geometric realization of the graph. This suggests a notion of “graph with boundary” and what their adjacency matrices should be. All the standard comparison theorems about eigenvalues of the Laplacian and nodal regions of eigenfunctions of the Laplacian carry over verbatim to graphs.

In particular there is a precise graph analogue of the fact that when Dirichlet eigenfuctions of the Laplacian on manifolds are restricted to any of their nodal regions, they give the first Dirichlet eigenfunction of that region. We use this property to study some aspects of eigenfunctions and eigenvalues in what follows. We show, in section 3, that a d-regular graph for d ≥ 3 of diameter 2k has a second eigenvalue of at least 2\sqrt{d − 1}(1 − π^{2}/(2k^{2}) + O(k^{4})); the proof can be stated in elementary terms, but we use the language of section 2 partly to point out the relationship with the classical eigenvalue estimating techniques.

In section 4 we discuss isoperimetric aspects of subgraphs of the d-regular infinite tree. Here the situation is much different than the analogue, in analysis, namely for subdomains of R^{n}, at least for classical isoperimetric problems. However, we conjecture that an analogue of the Faber-Krahn inequality holds for subgraphs of the d-regular infinite tree, and prove a weaker form of the conjecture. In section 6 we discuss the problem of when a second eigenvalue can “persist” in covers of the graphs. We give an example of a case where the second eigenvalue persists in an infinite set of covers. Such examples yield somewhat unusual nodal regions, and we conjecture that this behavior is exceptional. We remark on its connections to “Ramanujan graphs” and number theory.

In the process of discussing the fiber product, used in section 6 and later, we formulate some notions of covering theory and Galois theory for graphs in section 5. Such theories are more or less known, we give a precise and concise formulation which is also somewhat more general than typical formulations. In order to do so we introduce some new notions such as a generalized graph and a pregraph. As a corollary we give a concise proof of a theorem of T. Leighton on covers of graphs.

In section 7 we make a numerical study of the fiber product operation, on some very simple “Ramanujan graphs.” The fiber product is quite simple to work with (e.g. on a computer). By forming “twisted” fiber products we make the empirical observation that twisting sometimes reduces the second eigenvalue, yielding graphs with comparitively small second eigenvalue (e.g. it seems hard to find graphs of the same number of vertices and degree with second eigenvalue as small). We compare these to random graphs and graphs obtained by heuristic search, and in the process note some interesting properties of the random graphs’ second eigenvalue.

In section 8 we discuss other directions suggested by this work and some questions unsolved in this investigation.

In appendix A we gather some background for the techniques used in this paper. In the first part we review Shannon’s algorithm for capacity calculations. In the latter part we explain the eigenvalue comparison theorems in the context needed here; this is virtually identical to the classical theory (from analysis).

Throughout the paper we use the following convention: given an undirected graph, G, on n nodes, we denote by λ_{i} = λ_{i}(G) the i-th eigenvalue of the adjacency matrix of G arranged in non-increasing order, i.e. λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n}. By the second eigenvalue, denoted λ = λ(G), we mean the largest in absolute value among λ_{2}, …, λ_{n}; the spectral radius, denoted ρ = ρ(G), is just |λ|. When we speak of second eigenvalue, etc. it will always be the case that G is a d-regular graph and so λ_{1} = d.

It is well know that many theorems about eigenvalues of Laplacians on manifolds have graph analogues. Also certain more geometric notions, such as potential theory, have been traslated and applied to classical graph situations (typically to analyze infinite graphs or trees, such as in [Car72], [Dod84]). Part of what we do here is to point out that one sometimes needs to enlarge the class of graphs under consideration to those with boundaries^{1}, and that using this one can view graph eigenvectors as eigenfunctions on a geometric object. Such concepts, and the concept of fiber products, give rise to notions which can shed light on questions concerning the eigenvalues. We hope that more can be learned from this approach, and that this might be helpful in studying eigenvalue and isoperimetric type problems on graphs.

2 Nodal Regions of Graph Eigenfunctions

We recall the standard definitions of graph eigenvalues and eigenvectors (see [Alo86] or [CDS79] for details). Let G = (V, E) be an undirected graph. The Laplacian of G is the matrix Δ = D − A, where A is the adjacency matrix of G and D is the diagonal matrix whose diagonal entries are the degrees of the vertices; the non-negativity of its eigenvalues, 0 = ν_{1} ≤ ν_{2} ≤ ⋯ ≤ ν_{n} follows from that of its associated Rayleigh quotient on real-valued functions f on V,

R_{Δ}(f) ≡ \frac{(Δf, f)}{(f, f)} = \frac{∑_{(u,v)∈E}(f(u) − f(v))^{2}}{∑_{v∈V} (f(v))^{2}} ≥ 0,

where ( , ) is the L^{2}(V) inner product, the above equality being an easy calculation. If G is d-regular, i.e. each vertex has degree d, then A and Δ have the same eigenvectors, and the eigenvalues of A, d = λ_{1} ≥ ⋯ ≥ λ_{n} satisfy ν_{i} = d − λ_{i}.

Let G = (V, E) be an undirected graph. The geometric realization of G is the metric space G consisting of V along with an interval of length 1 glued in between u and v for every edge (u, v) ∈ E. By abuse of notation we speak of edges e ∈ E and vertices v ∈ V as their images in G. G looks like a one-dimensional manifold except at the vertices; in particular, we can define the notion of differentiability of a function at points in G − V.

1We remark that a notion of a graph with boundary appears, at least implicitly, in [Dod84]. However, the treatment there deals with boundary edges of length one, in our terminology. For dealing with nodal regions it is essential to allow boundary edges of fractional length.

Let μ_{1} be the measure on G which counts the number of vertices, and let μ_{2} be the measure which restricts to Lebesgue measure on each edge interval. Let H denote the set of continuous functions on G which are differentiable on all but a finite subset, S, of points of G (where S contains V). For f ∈ H we define its Rayleigh quotient to be

R(f) = \frac{∫_{G} |∇f|^{2} dμ_{2}}{∫_{G} f^{2} dμ_{1}}

(see [CH53] or [Gar66] for a discussion of the classical situation). A minizing sequence for R is any sequence of functions f_{1}, f_{2}, ⋯ such that f_{i} acheives the infimum R value among all nonzero f ∈ H which are μ_{1} orthogonal to f_{1}, …, f_{i−1}. The f_{i}’s are also called eigenfunctions, and the resulting values λ_{i} = R(f_{i}) are called the eigenvalues of R. We shall soon see that minimizing sequences exists; given this, it is easy to check that λ_{i} is independent of the choice of minizing sequence, as is the subspace E_{λ} ∈ H spanned by f_{i} such that R(f_{i}) = λ. What differs here from the classical situation is that μ_{1} is supported on n = |V | points, and so it only makes sense to speak of the first n eigenvalues and eigenfunctions. If f is non-zero and μ_{1} orthogonal to the first n term of a minimizing sequence, then f vanishes on V and so, in some sense, R(f) = +∞; one can take this as a definition, e.g. so that λ_{i} = +∞ for i > n, but this is of little concern to us.

By an edgewise linear function we mean a function f ∈ H whose restriction to each edge is a linear function.

Proposition 2.1 Among all f ∈ H with given values at the vertices, R(f) is minized at and only at the edgewise linear function with those vertex values. In particular the eigenvalues and eigenfunctions of R exist (i.e. minimizing sequences exist) and are those of the Laplacian of G (i.e. the restriction of R eigenfunctions to V are the Laplacian eigenvectors).

Proof The first statement follows from the easy fact that ∫_{0}^{1}(f′)^{2} dx subject to f(0) = a, f(1) = b is minized (over any reasonable class of functions) precisely when f is linear. For edgewise linear functions R and R_{Δ} agree, and the second statement follows from linear algebra (using the self-adjointness of the Laplacian on L^{2}(V)).

□

The nodal regions of an eigenfunction f of R are the connected components of f^{−1}(R − {0}). According to the classical theory f restricted to any of its nodal regions should be the first eigenvalue of the nodal region. So we must define what a graph with boundary should mean.

By a graph with boundary we mean an undirected graph G = (V ∪∂V, E ∪∂E) along with a “length,” c_{e} ∈ (0, 1], for each edge in e ∈ ∂E such that each E edge has both endpoints in V and each ∂E edge has exactly one endpoint in V and one in ∂V. We refer to V and ∂V vertices as interior and boundary vertices, respectively; similarly for the edges. By the geometric realization, G, of G we mean the metric space as before except that for each e ∈ ∂E edge we glue in an interval of length c_{e}. We define μ_{1} to be the measure which counts points in V, and μ_{2} as Lebesgue measure on E ∪ ∂E. We define R and H as before; we define H_{0} to be the subspaces of functions in H which vanish at ∂V. Notice that if e = {v, v′} is a ∂E edge with v ∈ V, then if f is linear along e we have

∫_{e} |∇f|^{2} dμ_{2} = ∫_{e}(f(v) − f(v′))^{2}/c_{e}^{2} dμ_{2} = (f(v) − f(v′))^{2}/c_{e}.

For this reason we set Δ_{0} = D_{0} − A where A is the adjacency matrix restricted to V and where D_{0} is the diagonal matrix whose entry corresponding to v ∈ V is

(D_{0})_{v,v} = ∑_{e∋v} \frac{1}{c_{e}}  (2.1)

with c_{e} taken to be 1 for e ∈ E. An easy calculation shows that the associated Rayleigh quotient, R_{Δ_{0}}, agrees with R on the set of edgewise linear functions in H_{0}. Again, minizing sequences for R restricted to H_{0} exist and are edgewise linear; we call the associated eigenvalues and eigenfunctions the Dirichlet eigenvalues and eigenfunctions; they are those of Δ_{0} (when restricted to V). In summary we have

The reader will note that the set ∂V plays no essential role in defining the Dirichlet eigenpairs; one can assume ∂V consists of one point, or that it has a distinct vertex for each ∂E edge, without affecting matters. In the latter case we say that G has separated boundary.

Given that G has separated boundary, we define the Neumann eigenvalues and eigenfunctions as those corresponding to R on H. They exist, the eigenfunctions are constant along ∂E edges, and the eigenpairs are easily seen to be the same as those of Δ_{1} = D_{1}−A where D_{1} is the diagonal matrix on V whose corresponding v entry is the number of neighbors it has in V (i.e. Δ_{1} is just the usual Laplacian on V, ignoring all boundary edges and vertices). More generally we can define mixed boundary conditions; namely for each ∂E edge {v_{w}, w}, with w ∈ ∂V (we assume G is separated so that to each such w there corresponds only one v), we specify a boundary condition of one of the following forms: (1) Dirichlet, i.e. f(w) = 0, (2) Neumann, i.e. f(w) unrestricted, or (3) f(w) = a_{w}f(v_{w}) for some constant a_{w} ≥ 0. Again it is easy to see that for this subspace H′ of H eigenpairs exist and agree with a Laplacian Δ̃ = D̃ − A for D̃ the diagonal matrix whose entry at v is

(D̃)_{v,v} = ∑_{\{w|(v,w)∈∂E\}} \frac{|a_{w} − 1|}{c_{(v,w)}} + ∑_{\{e∈E|v∈e\}} 1

(with a_{w} being 0, 1 for Dirichlet and Neumann conditions respectively). The Neumann condition is the same as requiring f(w) = f(v_{w}), for this choice of f(w) minimizes the numerator of R without affecting the denominator. In the above we require a_{w} ≥ 0 so as to have f(w) and f(v_{w}) of the same sign; if not, we would have to define the notion of nodal region more carefully. In any case there is no essential loss of generality in assuming a_{w} ≥ 0, for D̃ depends only on the value of |a_{w} − 1|. In summary, we have shown:

Proposition 2.2 The Dirichlet eigenpairs of a graph with boundary, G, i.e. successive orthogonal minimizers of the R restricted to functions vanishing on the boundary of G, are the same as the eigenpairs of the matrix on interior vertices Δ_{0} = D_{0} −A as above, whose eigenfunctions are extended by edgewise linearity to functions on all of G. Similarly for Neumann and mixed boundary conditions on graphs with separated boundary, with Δ_{1} and Δ̃ defined as above.

If G_{1} and G_{2} are graphs with separated boundary, we say that G_{2} is an extension of G_{1}, written G_{1} ⊆ G_{2}, if there exists an isometric imbedding (i.e. 1 to 1) of the realization of G_{1} into G_{2} which preserves the degree of each interior vertex. In other words, G_{1} is obtained from G_{2} by declaring some of its interior vertices to be boundary vertices and by shortening some of the boundary edges’ lengths (and ignoring any edges now connecting two boundary vertices). We also say that G_{1} is contained in G_{2}. If G_{1} and G_{2} are connected graphs and the above embedding is not onto we say that G_{2} is a strict extension of G_{1}, written G_{1} ⊂ G_{2}. The concept of being a strict extension implies both graphs involved are connected. In the above situations, any boundary conditions on G_{2} induces boundary conditions on G_{1} by imposing Dirichlet conditions on all exterior vertices of G_{1} which are interior to G_{2}, and keeping the same a_{w}’s on all exterior vertices, w, of G_{1} which are also exterior vertices of G_{2}; we call these the Dirichlet induced boundary conditions. We similarly define the Neumann induced boundary conditions.

We say that G_{1} ⊂ G_{2} freely if G_{1} ⊂ G_{2} with G_{2} − G_{1} having no cycles (i.e. is simply connected, i.e. every two points have at most one path joining them).

Given an eigenfunction of a graph, G, with any boundary conditions, each of its nodal regions determines a graph with boundary, G′; when there is no confusion we will identify a graph (possibly with boundary) with its realization.

At this point most of the classical theorems about monotonicity of eigenvalues as functions of the domain and of nodal regions of eigenfunctions go through essentially verbatim. In the below “eigenfunction” means an eigenfunction with any boundary conditions, unless otherwise specified.

Theorem 2.3 The min-max and max-min principles hold for R acting on H or any subspace of H determined by some boudary conditions as mentioned above. The first eigenfunction of a connected graph has a strict sign on its interior vertices, i.e. all values on interior vertices are positive or all are negative; the first eigenvalue has multiplicity one, i.e. the first eigenfunction is uniquely determined up to scalar multiple; all higher eigenfunctions have both positive and negative values on interior vertices. Any nodal region G′ ⊂ G of an eigenfunction, f, on G of eigenvalue λ, has λ as its first eigenvalue with boundary conditions on G′ being those Dirichlet induced from G, and the restriction of f is the corresponding eigenfunction. If G_{1} ⊆ G_{2} then the k-th eigenvalue of G_{2} for given boundary conditions is ≤ that of G_{1} with the Dirichlet induced boundary conditions; in particular, this holds for the Dirichlet eigenvalues of G_{1}, G_{2}. Same with ⊂ and < for the first eigenvalue for any boundary conditions on G_{2} except the Neumann condition (on all exterior vertices). The k-th Dirichlet eigenvalue is ≥ the k-th Neumann eigenvalue of a graph, with equality for the first eigenvalue iff the graph has no boundary. If some of the quantities |a_{w} − 1| in the mixed boundary conditions are increased, the eigenvalues cannot decrease; similarly if edges are added to the graph, and similarly if boundary edge lengths are decreased. If G_{1}, …, G_{r} are contained in G with disjoint interiors (i.e. intersecting only on boundary vertices), then the k-th smallest eigenvalue among all the G_{i} Dirichlet eigenvalues is ≥ the k-th Dirichlet eigenvalue of G; if the G_{i} exhaust G, then the reverse inequality holds for Neumann eigenvalues; the same holds for any boundary conditions on G, with respectively Dirichlet and Neumann induced boundary conditions on the G_{i}.

Proof This follows verbatim from the classical theory (see, say, [CH53] or [Gar66]). In any case all statements are easy, and we include their proof in the appendix.

□

We remark that the situation with graphs can exhibit some phenomenon not present in analysis. For one thing, the “Hilbert nodal region theorem” is not true without modification. For example, a star on n nodes, i.e. a graph which is a tree with exactly one interior vertex, has a second eigenfunction with n − 1 nodal regions. Of course, the problem is that there are boundary points of nodal regions which meet more than two nodal regions (such points are necessarily vertices), and, as in a star, it can happen that there are nodal regions whose only common boundary points with other nodal regions are of this form. Define a weak nodal region to be an equivalence class of points where p ∼ q iff p can be joined to q by a path along which f is everywhere non-positive or everywhere non-negative. The number of weak nodal regions is less than or equal to the number of nodal regions, equality always holding when nodal regions meet only at non-vertex points.

Theorem 2.4 If a k-th eigenfunction has k + i nodal regions, i ≥ 1, then no two of them meet at a non-vertex point, and every vertex meets at least i + 1 nodal regions. In particular, the number of weak nodal regions of a k-th eigenfunction is always ≤ k.

Proof This follows from the classical nodal region theorem; see the appendix for the details.

□

Another way in which the situation with graphs differs from that in analysis is that eigenfunctions in a connected graph can vanish in balls of arbitrarily large radius (a tree of degree ≥ 3 at all interior vertices has eigenfunctions which are zero at all interior vertices and assumes values −1, 1, 0 at the leaves); in analysis all the eigenfunctions are necessarily analytic (see, for example, [GT83, Fri69]) and hence can’t vanish in any open set.

Similarly, if G_{1} ⊂ G_{2} it is not true that all the Dirichlet eigenvalues need strictly increase (which is true in analysis, again by analyticity, assuming G_{2} − G_{1} has nonempty interior); similarly many of the theorems of strict inequality of eigenvalues don’t apply in general to graphs.

For an example of this phenomenon, consider an “hour glass” type graph, G: fix two isomorphic connected graphs, H_{1}, H_{2}, and fix v_{i} ∈ H_{i} which correspond to each other under the isomorphism. Let G consist of the H_{i} and an extra vertex v and the two extra edges (v, v_{1}) and (v, v_{2}). Denote by H′_{i} the graph H_{i} union the boundary edge (v_{i}, v); and denote its first Dirichlet eigenpair f, ν. We claim that the second Neumann eigenvalue of G is ν. Clearly the function which is f on H′_{1} and −f on H′_{2} is orthogonal to the first eigenfunction and achieves a Rayleigh quotient of ν. On the other hand, any eigenfunction with both positive and negative values has one of its nodal regions is contained strictly within one of the H′_{i}, having the same boundary conditions as those Dirichlet induced from H′_{i} (this follows from considering the eigenfunction’s value at v); thus no other second eigenfunction can have eigenvalue smaller than ν. On the other hand, if form G′ by adding a vertex w and the edge (v, w), then the same argument shows that ν is also the second Neumann eigenvalue of G′ (with eigenfunction as before and extended by zero to w). Hence a graph can strictly increase without the same being true for all its (Neumann, Dirichlet, etc.) eigenvalues.

In classical graph theory there is an “interlacing theorem” for the eigenvalues of the adjacency matrix (or Laplacian) of a graph, G, and any graph, G′, obtained by removing a vertex, v. That such a theorem holds for the Laplacian is contained in the above (half of this follows from the statement about Dirichlet eigenvalues when G′ ⊆ G, the other half follows from the last statement about comparing Neumann eigenvalues, taking G_{1} to be G with all edges to v being replaced by separate boundary edges, and taking G_{2} to consist of v).

The theorem that each k-th eigenfunction has at most k nodal regions is known as the Hilbert nodal region theorem. Some of the above results, including this one, can be stated (and proven) in elementary classical terminology of graphs— e.g. the induced subgraph on the vertex subset of positive eigenvector values, and that on negative values, have at most k connected components in total. However, for us it is important that the eigenfunction/value restricted to a nodal region is a first eigenfunction/value of that region, and for this the notion of a graph with boundary is essential.

Also, as in the classical case we can vary the boundary of G slightly and analyze the change in the eigenvalues and eigenfunctions. Similarly if we change, say, the coefficients of μ_{2} or μ_{1} (meaning we are allowed to weight the vertices differently). In analysis this is needed to prove more subtle theorems, such as what happens to Neumann eigenvalues when you change the domain. In the case of graphs such techniques are not needed for any theorem known to the author. For example, an easy argument gives:

Theorem 2.5 If G_{1} ⊆ G_{2} freely, then the k-th Neumann eigenvalue of G_{1} is at least that of G_{2}.

Proof If G_{1} ⊆ G_{2} freely, and G_{2} has exactly l more interior vertices than G_{1}, then their Laplacian matrices (i.e. G_{1}’s extended by zero to the additional interior vertices in G_{2}) differ by a matrix, M, which is the sum of l matrices, each vanishing on all but two columns and rows where it is of the form

[ \begin{matrix}1 & −1 \\ −1 & 1 \end{matrix} ] .

Hence M is a positive semi-definite matrix of rank ≤ l (actually = l in this case), and the claim follows from the max-min principle.

□

Note that if G_{1} ⊆ G_{2} but not necessarily freely, then some of the Neumann eigenvalues of G_{2} can be smaller than those of G_{1}; indeed, if G_{1} is any d-regular graph (without boundary) and G_{2} is obtained by adding a vertex, v, with an edge to every G_{1} vertex, then each higher Neumann eigenfunction of G_{1}, f_{2}, f_{3}, ⋯ extends by zero on v to an eigenfunction on G_{2} with eigenvalue = 1+ the old eigenvalue. Taking just about any d-regular graph, such as a large cycle, then gives an example of non-monotonicity in this situation.

One does not need to insist on separated boundaries to define Neumann and other boundary conditions. Indeed one can define Laplacians, and much of the above theory goes through. On the other hand, as the example in the previous paragraph suggests, monotonicity theorems for such boundary conditions often require free containment, and non-free containment can enlarge the eigenvalues (much as does adding edges to a graph).

We also remark that in analysis, the Neumann eigenvalues can increase when increasing the size of the domain, even in R^{2}, as shown by an example such as that of [CH53], chapter VI, section 2.6. Namely, if two fixed squares are joined by a very thin rectangle, then as the thinness tends to zero the second Neumann eigenvalue tends to zero; however, this family of domains are contained in some large fixed rectangle, whose second Neumann eigenvalue is > 0.

The technique of comparing two graphs by a smoothly varying family of graphs from one to the other seems quite interesting and yields another proof of the above theorem. Furthermore, we will need the version of it which holds for the Dirichlet boundary conditions later in this paper.

Theorem 2.6 Let G be a graph with boundary, having Dirichlet eigenvalues ν_{1} ≤ ⋯ ≤ ν_{n} with corresponding eigenfunctions f_{1}, …, f_{n}. Let σ be any real valued function on the boundary edges, and for ϵ > 0 let G_{ϵ} be the graph obtained from G by adding ϵσ(e) to the length of e for each boundary edge, e (we therefore assume σ is non-negative if c_{e} = 0, non-positive if c_{e} = 1). Then for all i ≤ n we have ν_{i}(G_{ϵ}) is differentiable in ϵ with

\frac{∂ν_{i}(G_{ϵ})}{∂ϵ}|_{ϵ=0} = ∑_{e∈∂E} σ(e) (\frac{∂f}{∂η} (e))^{2} ,

where ∂/∂η denotes the normal derivative of f at e, i.e. in the direction from interior to exterior vertex.

The above formula, with the summation over ∂E replaced by integration over the boudnary of a domain and with ∂/∂η interpreted as the normal derivative is just the classical variational formula for Dirichlet eigenvalues. Proof Perturbation theory tells us that if a symmetric matrix, M(ϵ) = M_{0}+ϵM_{1}+O(ϵ^{2}) has entries which are analytic functions in ϵ near 0, then the i-th eigenvalue ν_{i} of M is analytic in ϵ near 0 and

\frac{d}{dϵ}ν_{i} = (M_{1}v_{i}, v_{i})

with v_{i} the i-th eigenfunction normalized to be of unit length. The ν_{i}(G_{ϵ})’s are given as the eigenvalues of the matrix Δ_{0}(ϵ) = D_{0}(ϵ) − A, with D_{0}(ϵ) given in equation 2.1, with all c_{e}’s being linear functions of ϵ. It follows that the ν_{i}’s are locally analytic in ϵ. It suffices to verify the above formula for σ taking only one non-zero value, and this is a simple calcultion based on the above equation.

□

The above nodal region theory also allows us to generalize certain theorems from graph theory. For example, for a d-regular graph without boundary, G, λ_{2}(G) is related to its second Neumann eigenvalue, ν_{2}, via λ_{2} = d−ν_{2}. Dodziuk, in [Dod84], proves a Cheeger type inequality for the first Dirichlet eigenvalue of a d-regular graph with, in our terminlogy, all boudnary edges of length one. While the proof given there does not directly apply to ν_{2} or λ_{2}, the theorem still applies to λ_{2} via the above theory. Namely, if G′ is the nodal region of the second Neumann eigenfunction with the least number of vertices, then the graph G̃ obtained grom G′ by making all boundary edges of length one has first Dirichlet eigenvalue no greater than ν_{2}; on the other hand Dodziuk’s result applies to G̃, and thus yields a Cheeger type inequality for λ_{2} in terms of the “magnification” constant (as in [Alo86]). This gives a proof of a Cheeger type inequality for λ_{2} which is very similar to the proof in analysis; Alon’s theorem, in [Alo86], yields a better bound on λ_{2}, but his proof is trickier.

3 Eigenvalue Upper/Lower Bounds and Capacity

We restate part of theorem 2.3, which will be used to obtain lower bounds on λ_{2}. In this section we apply this only to graphs with boundary of length 1, where it is also follows from elementary linear algebra. This trick was exploited by Weyl in his proof of the growth rate of eigenvalues of the Laplacian.

Proposition 3.1 Let G_{1}, …, G_{s} be graphs with boundary which are disjointly (i.e. with disjoint interiors) contained in G. Then the number of Dirichlet eigenvalues of G which are ≤ λ for any λ is at least the total number of Dirichlet eigenvalues of the G_{i} which are ≤ λ.

Let T_{d,k} be the d-regular undirected tree of depth k; so T_{d,k} has a root and d(d − 1)^{i−1} vertices at distance i for each i ≤ k.

Proposition 3.2 The largest eigenvalue of T_{d,k}’s adjacency matrix is

λ_{1}^{d,k} = 2\sqrt{d − 1} cos θ_{d,k},

where θ_{d,k} is the smallest positive solution, θ, of g_{k}(θ) = d/(2d − 2), where

g_{k}(θ) ≡ \frac{sin((k + 1)θ) cos(θ)}{sin(kθ)}.

We have θ_{2,k} = π/(2k + 2), and for all d ≥ 3 we have θ_{d,k} ∈ [π/(k + 5), π/(k + 1)].

Proof For x ∈ T_{k} let ρ(x) denote x’s distance to the root. The function

f(x) = (d − 1)^{−ρ(x)/2} sin(π − (k + 1 − ρ(x))θ)  (3.1)

is positive on T_{k} provided that θ > 0 and π − (k + 1)θ > 0. Away from the root we have Af = λf with A the adjacency matrix and λ = 2\sqrt{d − 1} cos θ_{d,k}; at the root we have Af = λf provided that g_{k}(θ) = d/(2d − 2). Since g_{k}(π/(2k + 2)) = 1 and g_{k}(π/(k + 1)) = 0 (and g′_{k}(θ) < 0 on [π/(2k+2), π/(k+1)]), a θ making f a positive eigenfunction exists, and for this θ the Perron-Frobenius theorem (see the appendix) implies that the largest eigenvalue of T_{k} is f’s eigenvalue. An analysis of h(k) = g_{k}(π/(k + 5)) shows that h ≥ 4/5 for all k ≥ 1; indeed, setting s(x) = h(1/x) we check that s(0) = 4/5 and s′(x) has the same sign as 4 sin(α) − sin(4α) with α = 2πx/(1 + 5x); since α ≤ π/2 for all x ≥ 0, s is monotone increasing there, and so s(x) > 4/5 for x > 0.

□

For a non-negative symmetric square matrix (directed graph), its (average) valence^{2} is its largest positive eigenvalue (that of its adjacency matrix). The information theory literature usually speaks of the capacity, which is the log_{2} of the valence.

We say that a graph contains a d-regular ball of radius k if there exists a vertex v_{0} such that every vertex of distance < k has degree d. We note that among all such graphs, T_{d,k} has the smallest capacity.

Lemma 3.3 Let G contain a d-regular ball of radius k about a vertex v_{0}. Then the capacity of G is at least that of T_{d,k} (with equality iff G is isomorphic to T_{d,k}).

Proof Clearly there exists a local isomorphism of T_{d,k} into G; fix one such, say ϕ. Via ϕ, every walk from the root, r, of T_{d,k} to itself gives rise to a walk in G from v_{0} to itself of the same length, and this map is one to one. The capacity inequality follows by Shannon’s algorithm (see the appendix) or by considering traces of high powers of the adjacency matrices; strict inequality when G is not T_{d,k} follows from Shannon’s algorithm.

□

Definition 3.4 A graph with boundary is d-regular if every interior vertex has degree d. We then define its (average) valence to be d − ν_{1}, where ν_{1} is its first Dirichlet eigenvalue.

Since the first Dirichlet eigenfunction is positive on the vertices, d − ν_{1} is also the average valence (see the appendix) of the matrix

dI − Δ_{0}(G) = A_{0}(G) = A(G) − L(G)

2We adopt the terminology in [AFKM86], except that we will almost always omit the word average. In the information theory literature the word capacity is reserved for the log_{2} of this quantity.

where I is the identity matrix, Δ_{0} is as in section 2, A is the adjacency matrix restricted to V, and L is the diagonal matrix whose diagonal entry at v is

∑_{e∋v} (\frac{1}{c_{e}} − 1) .

(In the above the sum can be taken over only ∂E edges since the summand vanishes at E edges.) In particular we see that the usual notion of valence of an adjacency matrix coincides with this definition in that:

Proposition 3.5 If all of the ∂E edges have length 1, then L = 0 and the valence of G is just the valence of A.

Corollary 3.6 Let G be a d-regular graph with a subset of r points each of distance ≥ 2k from one another. Then λ_{r}(G) ≥ λ_{1}^{d,k}.

Corollary 3.7 For a d-regular graph on n vertices with d ≥ 3, the r +1-th largest eigenvalue is at least

2\sqrt{d − 1}(1 − \frac{π^{2}}{2k^{2}} + O(k^{−4})).

where k = (log_{d−1}(n/r))/2.

We can give a weaker but elementary version of the above corollaries, by noting that the function which is zero for ρ(x) > k and otherwise equal to f(x) as in equation 3.1 with θ = π/(2k + 2) = θ_{2,k} satisfies Af ≥ λf with λ = 2\sqrt{d − 1} cos θ. If G has no odd length cycles of length ≤ 2k then using the function (−1)^{ρ(x)}f(x) shows that:

Proposition 3.8 If G is a d-regular graph with a subset of r points each of distance ≥ 2k from one another, and contains no odd cycle of length ≤ 2k, then λ_{n−r}(G) ≤ −λ_{1}^{2,k} =

2\sqrt{d − 1}(1 − \frac{2π^{2}}{k^{2}} + O(k^{−4})).

This also gives an easy proof of the last corollary with a slightly worse k^{−2} constant.

We remark that under very weak assumptions about the graph, much more is true. Namely, given a sequence, G_{1}, G_{2}, … of d-regular graphs whose number of vertices, n_{i} = |V_{i}| goes to infinity, such that the number of cycles of length k is o(n) for every fixed k, then the eigenvalue distribution converges weakly to a distribution depending only on d (see [McK81], also [LPS88]).

For an arbitrary d-regular graph on n vertices, G_{n,d}, it is easy to see that λ_{2} ≥ \sqrt{d(n − d)/(n − 1)} by considering a vertex and the n − d vertices to which it is not connected. The fact that lim inf of λ_{2}(G_{n,d}) tends to 2\sqrt{d − 1} for fixed d as n → ∞ appears in many places (implicitly in [McK81], perhaps earlier). The first explicit mention of of a lower bound on λ_{2} in term of d and n occurs in Alon’s paper [Alo86], as to due himself and Boppana; later he gives a correct statement and a proof, in [Nil91], of a 2\sqrt{d − 1}(1 − O(1/k)) lower bound on λ_{2}. The fact that one can replace O(1/k) with O(1/k^{2}) seems to have been unnoticed in the literature^{3}. A. Lubotzky has pointed out to the author that the fact that the lim inf of λ_{r} tends to 2\sqrt{d − 1} for fixed r and d as n → ∞ has also been observed by M. Burger.

4 Towards a Faber-Krahn Type Inequality

To understand d-regular graphs better we wish to study isoperimetric type problems on the dregular infinite tree, T_{d}. For one thing, every d-regular graph is a quotient of T_{d}. For another, any graph with no short cycles looks locally like a tree, and so results on T_{d} will translate into results for isoperimetric problems restricted to small sets in the graph. Futhermore, many graphs with good isoperimetric properties, such as being expanders, contain no short cycles (see, e.g., [Chu88, LPS88] and proposition 4.2); intuitively speaking, a graph which expands well should have no simple unforced relationships between its edges, and hence should contain no short cycles.

Our experience from Euclidean space (or discretized versions of it), in which the best sets with respect to almost any type of isoperimetric problems are balls, is certainly not true in T_{d}. Indeed, for a subset of vertices, A, of T_{d}, let Γ(A) denote set of vertices connected to A by an edge, and let E(A, A′) be the set of edges with one endpoint in A and one in, A′, the complement of A. It is typical to ask for an A of a given size, how small can |Γ(A) − A| or |E(A, A′)| be and what are the sets A which achieve these values. It is easy to see that any connected set is an isoperimetrical extremal set in this sense.

Proposition 4.1 For any nonempty subset of vertices, A, of T_{d}, we have

|Γ(A) − A| = (d − 2)(|A| − 2) + 2(d − 1) − c̃, |E(A, A′)| = (d − 2)(|A| − 2) + 2(d − 1) − 2c

with c, c̃ ≥ 0; more precisely, c is the number of connected components of A (as an induced subgraph of T_{d}) minus one, and c̃ ≥ c is 2c minus the number of pairs of connected components of A whose distance is 2.

As a corollary we get results such as:

Proposition 4.2 In a d-regular graph whose shortest cycle is of length ℓ ≥, respectively, 5 and 4, among all sets of size ℓ, A, the ones minizing, respectively, |Γ(A) − A| and |E(A, A′)|, are precisely those cycles of length ℓ.

So in finite graphs without small cycles, good isoperimetric sets can be very “thin sets.”

Closer to our intution about Euclidean space, we conjecture that a Faber-Krahn type inequality holds in T_{d}. Namely, for an open subset G of T_{d}, let ν_{1}, the first Dirichlet eigenvalue of G, be the minimizer of the Rayleigh quotient among nonzero T_{d} functions vanishing outside of the interior of G (so that ν_{1} = ∞ if G contains no vertices); this is the same as the first Dirichlet eigenvalue of G viewed as a graph with boundary, where all components of G not containing a vertex are discarded. In this way it is easy to see that ν_{1} is continuous as a function of G in the metric ρ(G, G′) = μ_{2}(G − G′) + μ_{2}(G′ − G) where μ_{2} is the measure of section 2 (and where the range, the non-negative reals union ∞, is topologized as usual).

3The author has recently learned that N. Kahale has also observed this fact.

For any p ∈ T_{d}, not necessarily a vertex, and r > 0, the set of all points of distance ≤ r from p, B_{r}(p), determines a subgraph of T_{d} with boundary assuming B_{r}(p) contains at least one vertex.

Conjecture 4.3 Among all G ⊂ T_{d} with μ_{2}(G) = S fixed, the first Dirichlet eigenvalue, ν_{1}(G), is minimized when and only when G is a ball centered at a vertex.

We remark that a graph with boundary, G, is isomorphic to a subgraph of T_{d} iff it is d-regular and is a tree.

At present we can only prove a weaker statement:

Theorem 4.4 For any fixed S > 0, there is a G_{S} ⊂ T_{d} of μ_{2}-measure S whose ν_{1} attains the infimum over all ν_{1}’s of graphs with μ_{2}-measure S. Any such G_{S} is connected. Assuming d ≥ 5, for any R there is an S_{0} such that any G_{S} with S ≥ S_{0} contains a ball of radius ≥ R.

Proof Let G be a subgraph of T_{d}. If G has more than one connected component, then ν_{1}(G) is clearly the smallest ν_{1}(G′) ranging over all connected components, G′, of G. By theorem 2.3, ν_{1}(G) would strictly decrease if we replaced G by any connected subgraph of T_{d} strinctly containing G′; such as subgraph can be chosen to have measure g = μ_{2}(G).

So consider a sequence G_{1}, G_{2}, … of graphs of μ_{2}-measure S whose ν_{1} tends to the infimum. We can assume the G_{i} are connected, by the above.

Consider all pairs (G, p) of a connected subgraph of T_{d}, G, of μ_{2}-measure S with a point p ∈ G. We can specify all pairs (G, p), up to isomorphism, via a finite set of bounded real coordinates, with ν_{1} being a continuous function of these coordinates (fix for each G an embedding into T_{d}, and for each “non-backtracking” path of length S from p in T_{d} define a coordinate on G by its length along that path). It follows from compactness that there exists a limit point, G, of G_{1}, G_{2}, …, with μ_{2}(G) = S, and by continuity G attains the infimum of ν_{1}.

Now fix any G of μ_{2}-measure S minizing ν_{1} (which is necessarily connected by the above), and let f be a corresponding eigenfunction. Theorem 2.6 implies that the normal derivative of f at all boundary edges is the same. Hence we can take this to be 1 by rescaling f (this means that f is positive in the interior of G). This fact alone gives us some symmetries in G; namely, all boundary edges to a fixed vertex v necessarily have the same length, c_{v}, and furthermore f(v) = c_{v}.

To obtain more symmetries it is helpful to note:

Lemma 4.5 There is no geodesic path of vertices p = (v_{1}, v_{2}, …, v_{r}) in G such that for some i < j < k we have f(v_{j}) is less than both f(v_{i}) and f(v_{k}).

Corollary 4.6 Let w be a maximum of f on G. Then along any geodesic from w to a boundary vertex, f is non-increasing.

Here we say a path is geodesic if it is the shortest path joining its endpoints (this path is always unique in a tree). Proof For the lemma, first of all, we may assume by extending p that v_{1} and v_{r} are boundary vertices. Notice that since G is a subgraph of T_{d}, G consists of the path p plus trees T_{i} rooted at v_{i} for 2 ≤ i ≤ r − 1, each of degree d − 2. Given a permutation, σ, of {2, …, r − 1} we can form a new graph G_{σ} consisting of the path p_{σ} = (v_{1}, v_{σ(2)}, …, v_{σ(r−1)}, v_{r}) and attaching T_{i} to v_{i} as before; G_{σ} is a d-regular graph with boundary of the same μ_{2} measure as G. We can define f_{σ} as the edgewise linear function coming from the values of f at the vertices in the obvious way; ν_{1} of G_{σ} will certainly be less than that of G if the integral of |∇f_{σ}|^{2} along p_{σ} is less than than of |∇f|^{2} along p (since the μ_{1} integral of f^{2} and f_{σ}^{2} are clearly equal). It suffices to show that such a σ exists under the assumption of the lemma.

So let m_{1}, m_{2} denote the respective maxima of f from v_{1} to v_{j} and from v_{j} to v_{r}. We can assume m_{1} ≤ m_{2}. Let i_{1} < i_{2} < j be two integers such that f(v_{n}) = m_{1} for i_{1} ≤ n ≤ i_{2} and f(v_{n}) < m_{1} for n = i_{1} − 1 and n = i_{2} + 1. Let k_{1} > j be any integer such that f(v_{k_{1}}) ≤ m_{1} ≤ f(v_{k_{1}+1}). Let σ be the permutation formed by removing the interval [i_{1}, i_{2}] and pasting it in between k_{1} and k_{1} + 1. Then an easy calculation shows that σ is of the desired type, i.e. ν_{1}(G_{σ}) < ν_{1}(G); indeed, if ϵ_{1} = m_{1} − f(v_{i_{1}−1}), ϵ_{2} = m_{1} − f(v_{i_{2}+1}), ϵ_{3} = m_{1} − f(v_{k_{1}}), ϵ_{4} = f(v_{k_{1}+1}) − m_{1}, then ϵ_{i} ≥ 0 and ϵ_{1}, ϵ_{2} > 0, and the calculation boils down to the fact that

ϵ_{1}^{2} + ϵ_{2}^{2} + (ϵ_{3} + ϵ_{4})^{2} > (ϵ_{2} − ϵ_{1})^{2} + ϵ_{3}^{2} + ϵ_{4}^{2}.

The corollary follows immediately from the lemma.

□

Our general strategy is as follows. Let the maximum value of f occur at the vertex v. View v as the root of T_{d}, and consider the heights of all the other vertices of G (i.e. their distance to v). Let V_{1} be the set of “maximal height” interior vertices, i.e. interior vertices such that all of their edges away from v are boundary edges. We know that for each v ∈ V_{1}, the length of its d−1 boundary edges are the same, and if this value is c_{v} then also f(v) = c_{v}. This then determines the value of f at the parent of v, in terms of c_{v} and ν(G). We will be able to show that every child of this parent, like v, is an interior node with d − 1 boundary edges each of the same length as those of v. Our strategy is to prove that as we move up the tree from V_{1}, we will be able to claim that all interior vertices have balanced d − 1 regular trees ascending from them. We will be able to do this up to some given length, depending on the value of ν_{1}.

We make this description more precise as follows. For interior vertices v, w of G joined by an edge e, we say that v spawns a balanced tree at w of type (k, c) if all geodesics from w to boundary vertices through v are of length k + c, where k is an integer and c ∈ (0, 1]. This means that the connected component, T, of v in G − e, is a balanced (d − 1)-ary tree rooted at v in the usual sense, with all boundary edges of length c. The above shows that if w ∈ V_{2} is connected to a v ∈ V_{1} with all other neighbors of v being boundary vertices, then the tree spawned by v from w (in the usual sense) is balanced in the above sense. In this case the value of f, being an eigenfunction of the matrix D_{0} − A (as in equation 2.1), must satisfy

(1 + (d − 1)/c)f(v_{1}) − f(v_{2}) = νf(v_{1}),

i.e.

f(v_{2}) = c + (d − 1) − νc.

Similarly if v spawns a tree of type (k − 1, c) from w, then f(w) is given as f_{k} = f_{k}(c) determined by the recurrence relation

f_{i} = (d − ν)f_{i−1} − (d − 1)f_{i−2} ∀i ≥ 3, f_{1} = c, f_{2} = (d − 1) + (1 − ν)c.

This can be used to derive some weak symmetry properties of G. Notice that by theorem 3.2 and theorem 2.3 we know that ν > d − 2\sqrt{d − 1}.

Lemma 4.7 If v_{1}, v_{2} spawn balanced trees of type (k_{1}, c_{1}) and (k_{2}, c_{2}) from the same vertex w, then f_{k_{1}}(c_{1}) = f_{k_{2}}(c_{2}). In particular, if d ≥ 5 and ν = d − (2 + ϵ)\sqrt{d − 1}, then either (1) k_{1} = k_{2} and c_{1} = c_{2}, or (2) one of k_{1}, k_{2} is ≥ R(ϵ), with R a function of ϵ (independent of d) which → ∞ as ϵ → 0.

Proof The first statement is obvious. For the second part, note that (by induction on k) the functions f_{k}(c) are linear functions of c. Denote f_{k}(0), f_{k}(1) by α_{k}, β_{k}. We have f_{k}(c) = (1 − c)α_{k} + cβ_{k}. Let I_{k} be the interval with endpoints α_{k}, β_{k}. It suffices to show that I_{1}, ⋯, I_{R} are disjoint intervals none of which is a point (i.e. α_{k} ≠ β_{k} for 1 ≤ k ≤ R), for R = R(ϵ) as in the statement of the lemma.

Notice that α_{1} = 0, α_{2} = d − 1, α_{3} = (d − 1)(d − ν), and β_{1} = 1, β_{2} = d − ν. It then follows that α_{k+1} = (d − 1)β_{k} for k ≥ 1.

Let r_{k} = β_{k}/β_{k−1} for k ≥ 2. Now r_{2} = d − ν < d − 1 since d ≥ 5, and r_{k} satisfies

r_{k} = (d − ν) − \frac{d − 1}{r_{k−1}} ∀k ≥ 3.

It easily follows that r_{k} is decreasing in k while r_{k} is positive, and that the first k time r_{k} becomes nonpositive, r_{k+1} is positive (or undefined, if r_{k} = 0). In other words, r_{k} is decreasing at least until the first time when both β_{k} and α_{k} are non-positive. Since the first Dirichlet eigenfunction is positive at interior nodes, f_{k}(c) must be postive for all k ≤ K where K is the larger of k_{1}, k_{2}, which implies that d − 1 > r_{2} > ⋯ > r_{K}.

In particular we have α_{k} > β_{k} for k ≥ 2 and I_{1} = [0, 1], so none of the intervals I_{k}, k ≤ K, is a point. It suffices to show that β_{k} > α_{k−1} for k ≤ R(ϵ) to show that I_{1}, …, I_{R} are disjoint. Setting s_{k} = r_{k}/\sqrt{d − 1}, this reduces to showing that the sequence given by s_{2} = 2 + ϵ,

s_{k} = (2 + ϵ) − \frac{1}{s_{k−1}} ∀k ≥ 3

has s_{3} > ⋯ > s_{R} > 1 for R = R(ϵ). However at ϵ = 0 the s_{k} are just the Newton iterates for the equation (x − 1)^{2} = 0 at initial point x = 1, and so s_{R} > 1; hence for sufficiently small ϵ we have s_{R}(ϵ) > 1 as well.

□

The theorem follows at once, noting that for ν_{1}(G_{S}) tends to d − 2\sqrt{d − 1} as S → ∞ by theorem 3.2 and theorem 2.3.

□

We finish the section by noting that the same claim about f_{k_{1}}(c_{1}) = f_{k_{2}}(c_{2}) can be derived from Shannon’s algorithm. We outline how that calculation is performed.

Consider for B ∈ R the matrix M_{B} ≡ BI − Δ_{0} = BI + A − D_{0} where I is the identity matrix; for sufficiently large B this matrix will have all positive entries. Its largest eigenvalue is B − ν. Assume v spawns a balanced tree from w of type (k, c). By Shannon’s algorithm, z_{0} = 1/(B − ν) is the smallest positive root of the equation P_{w}^{G}(z) = 1. We may write P_{w}^{G} as the sum of P_{w,v} + P_{0}, with P_{w,v} representing the contribution from the walks through v, and P_{0} representing the other walks. By convention, if v is a boundary vertex connected to w by an edge of length c, we say v spawns a balanced tree of type (−1, c) from w.

Lemma 4.8 P_{w,v} is given by ϕ_{k_{i}}(c_{i}, z), where the ϕ_{k}’s are given by ϕ_{−1}(c) = −z/c, and for i ≥ 0,

ϕ_{i}(c, z) = z^{2} \frac{1}{1 − m_{i}(c, z)},

where the m_{i} are given by

m_{0}(c, z) = ((B − 1) − \frac{(d − 1)}{c}) z,

and for i ≥ 1

m_{i}(c, z) = (B − d)z + (d − 1)ϕ_{i−1}(c).

Proof Follows easily by induction on i.

Let v_{1}, v_{2} spawn trees from w as in lemma 4.7. As small change in c_{1}, c_{2} gives rise to a new graph, whose μ_{2} measure is the same as the original graph as long as

(d − 1)^{k_{1}}c_{1} + (d − 1)^{k_{2}}c_{2}

is preserved. The new graph cannot have a larger P_{w}^{G}(z_{0}), for if so it would have a larger B − ν and so a smaller ν. Hence we have

(d − 1)^{−k_{1}} \frac{∂}{∂c}ϕ(c_{1}, z_{0}) = (d − 1)^{−k_{2}} \frac{∂}{∂c}ϕ(c_{2}, z_{0}).

We wish to calculate under what circumstances this can occur.

To simplify the calculation, it will suffice to take a first order approximation to the above for large B. More precisely, set t = 1/(B − ν), which means that z_{0} = t, and consider the above equation for small t > 0. We have for i ≥ 1,

\frac{∂}{∂c}ϕ_{i} = z^{2} \frac{1}{(1 − m_{i})^{2}} \frac{∂}{∂c}m_{i},

and for i ≥ 2,

\frac{∂}{∂c}m_{i} = (d − 1)\frac{∂}{∂c}ϕ_{i−1}.

It then follows that:

Lemma 4.9 m_{i}(c, t) = 1 − tK_{i}(c) + O(t^{2}) where K_{i}(c) is the function given by

K_{i}(c) = d − ν − \frac{1}{K_{i−1}(c)} ∀i ≥ 1, K_{0}(c) = \frac{d − 1}{c} + 1 − ν.

For all j ≤ i, K_{j}(c) is necessarily non-negative. Furthermore, for all i ≥ 0,

\frac{∂}{∂c}ϕ_{i}(c, t) = \frac{(d − 1)^{1+i}}{c^{2}} \frac{1}{(K_{0}(c) ⋯ K_{i}(c))^{2}} t + O(t^{2}).

The formula remains valid for i = −1 (if we omit all the K’s).

Now it is easy to see that the product cK_{0}(c)K_{1}(c) ⋯ K_{i}(c) is just f_{i}(c), yielding an alternate derivation of the fact that f_{k_{1}}(c_{1}) = f_{k_{2}}(c_{2}).

5 Covering and Galois Theory

We explore some notions of covering theory and Galois theory for graphs. The connection of graph covers (or “factors”) with the spectum appears frequently in the literature (see, for example, [CDS79]). The notion of Galois theory appears less often in graph theory, but is well known to people studying analysis on trees (e.g. p-adic Lie groups), combinatorial group theory, etc., and probably appears in the literature in various places, at least implicitly, in say, [MKS66, CDS79, Ser80, GT87, DD89, Joh90]. It is a very simple Galois theory, and so we describe it here. It also gives rise to the notion of a fiber product^{4}, which can be used to generate some simple and interesting new graphs.

5.1 Notation for graphs and colorings

Recall that a directed graph is a a collection G = (V, E), where V and E are sets with each element e ∈ E having an associated ordered pair of vertices (ν_{1}(e), ν_{2}(e)). For brevity we often consider E as merely a multisubset of V × V (multisubset meaning that we can have “multiple edges,” i.e. different edges associated to the same pair of vertices), but we shall often need the former, more accurate definition to make things work. An edge with ν_{1}(e) = ν_{2}(e) is called a self-loop. Also a graph, by which we understand an undirected graph, has for each e ∈ E an associated subset ν(e) of size 2 or 1 (the lattter case being a self-loop).

4Perhaps “coupled product” would be more suggestive to, say, people working in Markov chains. Indeed, the walk on the fiber product, G_{1} ×_{G} G_{2}, viewed as a Markov chain, is just the simultaneous walk on the chains G_{1} and G_{2}, coupled according to G.

We denote {1, …, d} by [d]. By a d-coloring of a graph we mean a map of the edges of the graph to [d]; a proper d-coloring of a d-regular graph is one such that every vertex is incident upon exactly one edge of each color; for a d-regular directed graph we mean every vertex has one edge of each color terminating at it, and one of each color originating at it.

In the context of directed graphs, B_{d} denotes the boquet of d self-loops, i.e. the graph consisting of one vertex with d-self loops, which we identify with [d]. Thus a d-coloring is just a morphism to B_{d}. The classical definition of (undirected) graphs does not allow for d-colorings to be interpreted in this way, and we must correct the definition.

Indeed, the classical definition of an undirected graph allowing for self-loops has the following bizarre features: (1) in the adjacency matrix, the diagonal entry must be defined as twice the number of self-loops to make everything work, (2) the geometric realization of a point with one self-loop has a non-trivial automorphism, (3) a d-coloring is not the same as a map to some fixed graph. These are all part of the same problem, and there is a simple way to remedy all. We define a generalized undirected graph to be an directed graph, G = (V, E) along with an involution σ: E → E which reverses edges, i.e. ν_{i}(σ(e)) = ν_{2−i}(e). Thus a generalized graph can have a directed self-loop associated via σ to itself, which we call a half-loop; otherwise these graphs are the same a directed graphs. One can concisely view a half-loop as a self-loop with an orientation. All notions for directed graphs carry over to generalized graphs, with some added features. For example, for each half-loop we put a one in the corresponding diagonal entry of the adjacency matrix; as such, the resulting adjacency matrices that arise are precisely the set of symmetric matrices with non-negative integral entries. Also, for generalized graphs we have the boquet of d half-loops, B_{d}, having the property that a d-coloring is precisely a map to B_{d}.

5.2 Generalities about covers

In what follows a graph, G, is the geometric realization of a graph; so G is a metric space, having a distinguished set of points, V, set of subsets, E, etc. Working this way one can give concise definitions that work for all graphs, including those with multiple edges and self-loops. A directed graph is a graph where each edge, being isomorphic to a real interval, is given an orientation. A morphism of graphs is a metric preserving map mapping vertices to vertices; for directed graphs it should also preserve the orientations of the edges. The definitions also work for graphs with boundaries.

A morphism, ϕ: G_{1} → G_{2}, is a covering map if it is locally an isomorphism. A cover of G is a collection (H, ϕ) of a graph and a covering map; if G is connected then the number of inverse images of any point is the same, and is called the degree of the cover, denoted [H: G]. Covering induces a partial order on the set of graphs, namely H ≥ G if there exists a covering map, ϕ: H → G.

For any graph G there is a universal cover or a “largest cover,” (G̃, ϕ). G̃ is a tree, and its vertices can be identified with the set of “non-backtracking” walks from a fixed vertex, v ∈ G.

For graphs G_{1}, G_{2} over a graph G, i.e. which are given fixed homomorphisms ϕ_{i}: G_{i} → G, the fiber product, G_{1} ×_{G} G_{2} is given as the set of pairs, (x_{1}, x_{2}), x_{i} ∈ G_{i}, such that ϕ_{1}(x_{1}) = ϕ_{2}(x_{2}), viewed as a graph in the obvious way. If G_{1} and G_{2} are covers of G, then G_{1} ×_{G} G_{2} is a cover of G_{1} and of G_{2}.

The above notion coincides with the abstract notion of fiber product. Recall that for a fixed graph G one can consider the set of all graphs over G, and for any two such graphs, G_{1}, G_{2}, with fixed homomorphisms ϕ_{i}: G_{i} → G, one considers the set of “morphisms over G,” i.e. morphisms f: G_{1} → G_{2} such that ϕ_{2} ∘ f = ϕ_{1}. This is the category Gr_{G}. The fiber product is by definition an H over G_{1}, G_{2}, G which is universal in that every other H′ lying over the three has its projections factoring in a unique way through H; clearly it exists and is the above product.

We leave it as an exercise to the reader to give these definition in terms of traditional graph theory. The reader should remark that in figure 1, with a graph G having a self-loop, G_{1} is a cover of G and G_{2} isn’t. We remark that for directed graphs, the fiber product over

[figure: G; 1; G; 2; G; A graph.; A cover.; Not a cover.]

Figure 1: Graph covers for undirected graphs with self-loops.

B_{1} is just one of the standard products.

If π: H → G is a cover, and w_{1}, w_{2} are any two vertices of H lying over the same vertex in G, then there is a unique automorphism σ: H → H maping w_{1} to w_{2}. In particular the size of Aut(H/G), the group of automorphism of H over G, is equal to the degree.

If A is a group acting freely on a graph, G, then G/A is a graph, and is covered by G. The point here, of course, is that “freely,” by definition, means without fixed points on the geometric realization of G for non-trivial a ∈ A, which the reader can check is enough to guarentee a nice quotient (i.e. “regular quotient,” as in, say, [GT87]).

Let F be a commutative (finite) group, and let G be a graph. An F -torsor^{5} over G is a covering π: H → G with an isomorphism of F with Aut(H/G), i.e. a free action μ: F ×H → H of F on H which is trasitive on all points in H lying over a fixed point of G. The set of all F -torsors forms a group; namely for F -torsors H_{1}, H_{2}, we define H_{1} ×_{F} H_{2} to be H_{1} ×_{G} H_{2} modulo the free action of F, f ↦ μ_{1}(f, ·) × μ_{2}(f^{−1}, ·), i.e. modulo x_{1} × x_{2} ∼ μ_{1}(f, x_{1}) × μ_{2}(f^{−1}, x_{2}) for all f ∈ F. If F is not commutative one needs to modify this definition, insisting on left and right actions of F, in order to make ×_{F} associative.

5also called a principle F -bundle over G, a principle homogenous space, or a twisted form of F × G over G.

Although it is not needed here, we give the classical interpretation of torsors. We say that two torsors H_{1}, H_{2} are isomorphic if there is an isomorphism between them over G which commutes with the action of F. Topologically, we can consider the cohomology groups of G with coefficients in F, viewing G as, say, a CW-space (see [Mun84]). Since G is connected, we have H^{0}(G, F) ≃ F, and

H^{1}(G, F) ≃ F^{l}

where l is the number of loops in G, i.e. l = |E| − |V | + 1. The classical interpretation of torsors is that the set of F torsors over G modulo isomorphism is cannonically isomorphic to

Hom(π_{1}(G), F) ≃ H^{1}(G, F)

where π_{1} denotes the fundamental group. The group operation defined above on torsors is the same as the group operation on H^{1}(G, F).

A proper coloring of a d-regular (directed or undirected) graph is the same thing as a covering map from the graph to B_{d}. Hall’s theorem implies that any d-regular directed graph has a proper coloring. There is another way to get proper colorings, if one is willing to pass to covers of degree d, which we describe below.

A generalization of the notion of a graph needed here is one in which we specify certain data near each vertex, without the requirement of global consistency. By a pregraph we mean a collection P = (V, E = ⨿_{v∈V} E_{v}) of a set V and a collection of disjoint sets, E_{v}, one for each v ∈ V, such that each e ∈ E_{v} has a subset of vertices, ν(e), of size 2 or 1 associated to it containing v (⨿ denoting the disjoint union). A directed pregraph is defined analogously with directed edges E_{v} = E_{v,1}⨿E_{v,2} such that each e ∈ E_{v,i} has ν_{i}(e) = v. Given a directed or undirected graph, G = (V, E), the neighborhood, N(v), of a vertex v ∈ V, is defined to be the set of all edges incident upon v; we define the associated pregraph to be the graph P(G) = (V, ⨿N(v)); so P(G) has twice the number of edges that G has; in a directed graph, each self-loop, e with ν(e) = {v}, gives rise to two edges, one in each of E_{v,1}, E_{v,2}; for self-loops in graphs it is best to restrict to generalized graphs allowing only half-loops, and so the above discussion applies (in particular, each half-loop in the graph gives rise to two half-loops in the corresponding pregraph). Pregraphs arising from graphs are precisely those pregraphs with an edge-involution τ: E → E such that if e ∈ E_{v} and is incident on w ≠ v, then τ(e) ∈ E_{w} and is incident on w (and has the same orientation as e in the case of directed pregraphs). We will also need to work with generalized pregraphs, defined in the obvious way, namely as directed pregraphs with an edge involution σ taking e ∈ E_{v,i} with ν_{2−i}(e) = w to an edge e′ ∈ E_{w,2−i} with ν_{i}(e′) = v for all v, w, i.

For pregraphs we define morphisms and the fiber product in the obvious way, e.g. a morphism is a map from vertices to vertices and edges to edges with “incidence” relations preserved. Given a morphism π: P_{1} → P_{2} of pregraphs, we say P_{1} is a graph over P_{2} if we can find an edge-involution, σ, as above with π invariant under σ. We say that a morphism π: P_{1} → P_{2} of pregraphs is a covering map if for every vertex, v_{1} of P_{1}, π gives an isomorphism of E_{v} to E_{π(v)}. Given a d-regular graph, fix any cover π: P(G) → B_{d} (identifying B_{d} with its associated pregraph); this just means fix a bijection of [d] with the edges of N(v) for each vertex v of G (for directed graphs we fix bijections of [d] with the incoming edges of N(v) and with the outgoing edges of N(v)), without worrying about consistently coloring an edge in the possibly two different neighborhoods in which it appears. π will determine a (proper) d-coloring of G only if P(G) is a graph over B_{d}.

Fix an identification of the edges of B_{d} with μ_{d}, the group of d-th roots of unity (in C). Given the cover π: P(G) → B_{d}, consider the pregraph, P, covering P(G) whose vertices consist of all pairs, (v, ζ), and with E_{(v,ζ)} having one edge, (e, ζ), for each edge, e ∈ E_{v}, and define π̃((e, ζ)) = π(e)ζ. Then π̃: P → B_{d} and π_{2}: P → G have the property that each edge, e, of P(G) has π_{2}^{−1}(e) mapped bijectively to μ_{d} via π̃; because of this property P there is a unique edge involution on P compatible with that of P(G) making P a graph. Denoting this graph by G̃, we see that π̃ and π_{2} extend to graph covering maps; also G̃ is clearly a μ_{d} torsor of G. Finally note that while π ∘ π_{2} and π̃ are different maps of G̃ to B_{d} (unless d = 1), they do satisfy

π ∘ π_{2}(e)/π ∘ π_{2}(e′) = π̃(e)/π̃(e′) ∀v, ∀e, e′ ∈ N(v),

(with v ranging over all vertices of G̃).

The above construction works for directed and undirected graphs; it also has a natural generalization to undirected graphs. To explain it we need to specify the correct analogue of B_{d}. So, consider a finite graph, G, its universal cover, T, and the class of all graphs, G_{T}, with universal cover T. Unlike the class of d-regular graphs, there is no initial object in G_{T}, i.e. a B ∈ G_{T} such that all elements of G_{T} map to B. But there is an initial pregraph, B. Namely, we consider two vertices of T to be equivalent if there is an automorphism of T taking one vertex to the other; clearly there exists a unique pregraph B having one vertex for each equivalence class of T vertices and having edges so that there is a covering map of pregraphs π: P(T) → B. A graph G has a covering of P(G) to B iff G ∈ G_{T}; B is the correct analogue of B_{d} in the non-regular case.

In the undirected case, for vertices u, v ∈ B, let E(u, v) be the E_{u} edges with second endpoint being v, let d(u, v) = |E(u, v)|, fix an identification of E(u, v) with μ_{d(u,v)} for each u, v, and let D be the least common multiple of the d(u, v)’s; in the directed case we do the same with E_{i}(u, v), d_{i}(u, v) for i = 1, 2. The construction, generalized in the obvious way, gives:

Proposition 5.1 Let G be a graph with a covering map π: P(G) → B given. Given an identification, ι, of the edges of B with elements of μ_{D} as above, there is a natural μ_{D} torsor π_{2}: G̃ → G, and a natural map π̃: G̃ → μ_{D}. In addition, we have for any vertex, v, of G̃,

ι ∘ π ∘ π_{2}(e)/ι ∘ π ∘ π_{2}(e′) = π̃(e)/π̃(e′) ∀e, e′ ∈ N(v),

and each edge, e, of G̃ has π_{2}^{−1}(e) mapped bijectively to μ_{D} via π̃.

We get the following corollary:

Corollary 5.2 Any two finite graphs with the same universal cover have a common finite cover. If the number of vertices in the graphs are n_{1}, n_{2}, and D is the least common multiple of the degrees of the graphs (of the indegrees and outdegrees for directed graphs), then the cover can be taken to be of size ≤ Dn_{1}n_{2}.

Proof Given G^{1}, G^{2} over B as above, form μ_{D} torsors G̃^{i} as above. Then G̃^{1} ×_{μ_{D}} G̃^{2}, formed with respect to π̃^{i} (and deleting isolated vertices) is the desired cover.

□

The fact that any two finite graphs with the same universal cover have a common finite cover was originally proven by Leighton (see [Lei82]); presumably the above construction is the same as Leighton’s. Beforehand Angluin and Gardiner (in [AG81]) proved the above for d-regular undirected graphs, noticing that by Hall’s theorem any bipartite graph has a proper d-coloring; since any non-bipartite connected graph has a bipartite cover which is a μ_{2} torsor, the ×_{μ_{2}} construction shows that any d-regular graphs on n_{1}, n_{2} vertices have a common cover with ≤ 2n_{1}n_{2} vertices.

We finish this section by remarking on some other common covering constructions. Let Z_{d} be the directed Cayley graph with vertices μ_{d} on generator set {ζ} for some primitive d-th root of unity ζ. Then for any directed graph G we have a d-fold cover, G_{d} =^{def} G ×_{B_{1}} Z_{d}, of G which is a μ_{d} torsor. For d = 2 (and only d = 2) Z_{d} is a graph (i.e. generalized graph), and so for graphs G we have that G_{2} is a graph; G_{2} is a bipartite graph, for G connected G_{2} has either 2 or 1 connected components, according to whether or not G itself is bipartite, and in the latter case G_{2} is the “bipartite cover” of G.

5.3 Galois theory for regular directed graphs

The universal cover of the directed B_{d} is the directed d-regular infinite tree T_{d}, which may be thought of as the (directed) Cayley graph of the free group, F_{d}, on [d] = the set of edges of B_{d}, once we fix a root, r, of T_{d}. For any cover, G, of B_{d}, and any vertex v of G, there is a unique covering map, ϕ: T_{d} → V with ϕ(r) = v. The set H_{v} = ϕ^{−1}(v) is a subgroup of F_{d}, and G is the quotient graph T_{d}/H_{v} (i.e. graph of left cosets). For any other vertex, v′, of G, H_{v} and H_{v′} are conjugate subgroups.

The graph G is called Galois or normal if H_{v} is a normal subgroup, equivalently if H_{v} does not depend of v, or equivalently G is the Cayley graph of some group. All the stardard results of Galois type theories hold here. For example, any finite graph, G, has a finite Galois cover, i.e. is the quotient of a finite Cayley group with ≤ n^{n} vertices, where n is the number of vertices of G; indeed, H_{v} contains the normal subgroup

⋂_{[g]∈T/H_{v}} gH_{v}g^{−1}

which is clearly of index at most n^{n−1} in H_{v}. The reader can compare this Galois theory to that of first year algebra— a graph translates to a ring, a connected graph to a field, covers to field extensions, × translates to ×, etc. One can check that some well known identities in field theory, such as

L ×_{K} L = ⨁_{σ∈Gal(L/K)} L^{σ}

for Galois extensions L/K, hold for graphs as well (in fact, this identity points out why graphs correspond to rings, × to ×, etc.).

If G_{1}, G_{2} are connected Galois covers of a connected graph, G, then any connected component, H, of G_{1} ×_{G} G_{2} is a graph covering the former graphs; it is minimal in the sense that any graph which is a G-equivariant cover of G_{1} and of G_{2} is also a cover of H. Thus a “max” operation exists for the covering order in the subcategory Gal_{G} of Galois covers of Gr_{G}.

5.4 Galois theory for undirected graphs

For undirected graphs there are two typical Galois theories and Cayley graphs which arise. The first obtained by considering a d-regular graphs with a d-coloring of its edges, i.e. a graph, G, and a fixed morphism π: G → B_{d}, where B_{d} is the undirected boquet of d halfloops. The universal cover is the d-regular infinite tree, T_{d}, viewed as the Cayley graph with generators {g_{1}, …, g_{d}} with the underlying group being the free group on d generators, {g_{1}, …, g_{d}}, modulo the relations g_{i}^{2} = 1.

The second theory considers 2d-regular graphs, G, and fixed morphisms to W_{d}, the boquet of d self-loops, i.e. whole-loops, not half-loops, so that W_{d} is a 2d-regular graph. The universal cover, T_{d}, can be identified with the Cayley graph with generators {g_{1}, g_{1}^{−1} …, g_{d}, g_{d}^{−1}} with the underlying group being the free group on d generators, {g_{1}, …, g_{d}}; this identification involves fixing for each self-loop in W_{d} an orientation, corresponding to multiplication by g_{i}, (traversing the edge in reverse order corresponding to g_{i}^{−1}); in other words, we view W_{d} as consisting of d pairs of oppositely oriented half-loops, and color the half-loops with 2d colors, {g_{1}, g_{1}^{−1} …, g_{d}, g_{d}^{−1}} such that oppositely oriented pairs are colored g, g^{−1}. This type of Galois theory is probably the most common in applications.

The rest of Galois theory in these cases goes through pretty much as for directed graphs as in the previous section. There is a notable difference in the connection to graph theory, namely that, in the first type of Galois theory, not all d-regular graphs have a d-coloring. However, any d-regular graph has a covering which is d-colorable; one can use the μ_{d} torsor construction described previously, or one can apply Hall’s theorem to the bipartite cover of d. A similar remark applies to the second type of Galois theory.

5.5 Additional remarks

We remark that one can define more general Galois theories, but often much less can be said for such theories. Namely, given a graph G covering an pregraph, B, we can define G to be Galois if π_{1}(G, v) viewed as a subgroup of π_{1}(B, u), with u, v any vertices with v over u, is a normal subgroup. This definition is independent of u, v, but there is no general way to view G as a Cayley graph, especially when B is not regular. If B is regular but has more than one vertex, one can non-cannonically view G as a Cayley graph; an interesting simple example of this is when B has two vertices u, v, u having a half-loop and one edge to v, v having two edges to u; the resulting Cayley graphs will necessarily be non-commutative groups, due to the lack of homogeneity in B.

One might ask which pregraphs B admit graph covers or finite graph covers. Given a pregraph and vertices u, v, let d(u, v) denote the number of E_{u} edges with second endpoint being v. If d(u, v) ≠ 0 iff d(v, u) ≠ 0 for all u, v, then it is easy to see that B is covered by a tree (i.e. its universal graph cover), and clearly this condition is necessary if B is covered by a graph. If we let r(u, v) = d(u, v)/d(v, u) when defined, then in any finite graph covering B we must have r(u, v) is the ratio of the number of vertices over v to those over u; in particular we must have r(u, v)r(v, w) = r(u, w) when these numbers are defined. An easy argument shows that this condition suffices for B to have a finite cover, and that the degree can be taken to be the least common multiple of the d(u, v)’s.

We remark that not all aspects of field theory have graph counterparts in Galois theory. For example, we don’t know in what naturally arising sense a graph cover can be allowed to be “ramified.” Also some of the above has analogues for graphs which are not d-regular (but we cannot hope to realize the universal cover as a Cayley graph in any nice sense).

One should expect, as in all Galois/covering theories, to be able to study some aspects of a graph by considering its covers (e.g. section 4). For studying the spectrum, if H is a cover of G, of finite degree, then G’s eigenpairs pull back to eigenpairs of H; H’s eigenvectors push forward to vectors on G by summing over the inverse images of points in G, and eigenvectors of H not arising from pullbacks of eigenvectors on G are precisely those which push forward to 0. Covers of infinite degree present the unpleasantness that eigenvectors of the base graph do not lift to eigenvectors of finite L^{2} norm on the cover; relations between the spectra are not as exact as with finite covers. Thus it seems better in some cases to work with finite covers; the universal cover does not exist in this category, but, as usual, should be regarded as the inverse limit of all finite covers.

The same theory yields a covering/Galois theory for t-uniform hypergraphs (i.e. each e ∈ E is a set of vertices of fixed size, t) as quotients of hypertrees (see [Fri91]). This situation is a good example of where spectral aspects of the universal cover, the hypertree, which are relatively easy to analyze, are not known to have much bearing on questions about explicitly constructing their finite counterparts (in a way which yields small eigenvalues, good isoperimetric properties, etc.).

6 Coverings and Eigenvalues

We hope to obtain spectral information about a graph by studying the spectrum of its covers, at least to some extent (see [Bro86] for examples in analysis). If H is a covering (see appendix) of a connected graph G, then λ_{1}(H) = λ_{1}(G). While λ_{2}(H) ≥ λ_{2}(G) can hold with equality for some H, it seems unlikely that it would hold with equality for a fixed G and many H’s. We wish to discuss the following question:

Question 6.1 Let G be an undirected finite graph. Under what conditions can there exist connected covers of G, H_{i}, with size tending to infinity and with λ_{2}(H_{i}) = λ_{2}(G) for all i? Can one give geometric conditions on G and/or the sequence {H_{i}} to preclude this behavior?

At some point the author entertained the possibility that in any such situation one would have λ_{2}(H_{i}) > λ_{2}(G) for sufficiently large i, for the following reason. The theorem in the last section implies that for any d-regular graph with no small cycles, its subgraphs with smallest first Dirichlet eigenvalue among all subgraphs of their size contain large balls (depending on the size of the graph and the length of its shortest cycle). This leads us to believe that for large graphs of bounded degree (or at least for those with no short cycle), the nodal regions of the second eigenfunction should be of large inradius, i.e. should contain large balls.

On the other hand, the second eigenvector of G lifts to an eigenvector on H_{i} whose nodal regions’ inradii are bounded by those of the nodal regions on G. It seems unlikely, at least for graphs, H_{i}, with good isoperimetric properties, that their nodal regions would look “thin” in the above sense.

Unfortunately one can give examples to show that sometimes one can have λ_{2}(H_{i}) = λ_{2}(G) for all i. Namely, let T_{i} be any collection of d-regular graphs for some d whose λ_{2}’s are below a fixed constant λ, and let S be a d′-regular with λ_{2}(S)d > dλ (T_{i} can be taken to be graphs such as the Y^{p,q}’s described below with p fixed, and S then chosen to be a sufficiently large cycle graph). Then setting G = S ×_{B_{1}} B_{d} and H_{i} = S ×_{B_{1}} T_{i} gives such an example, since spectrum of G_{1} ×_{B_{1}} G_{2} is just the pointwise products of the spectra of G_{1}, G_{2}.

In the preceding example the graphs in question have quite bad expansion properties. It is conceivable that collections {H_{i}} with more typical geometric properties (i.e. like those of random graphs) never have a persistent λ_{2} as above.

P. Sarnak has pointed out to the author the connections between the above questions and number theory. Namely, in [Iha66] Ihara uses the Brandt-Eichler Zahlentheorie der Quaternionenalgebren to give various (p+1)-regular graphs with the property that its second eigenvalue is ≤ 2\sqrt{p}. Furthermore, all second and lower eigenvalues of these graphs are related to those of Frobenius in characteristic p acting on (the Jacobian of) the modular curve Y_{0}(ℓ) (see, e.g., [Sar]). In particular, the non-persistence of the second eigenvalue for these graphs would imply that no eigenvalue of Frobenius as above can be purely real and positive.

We recall a special case of these graphs which have a simple description and which we will use later for numerical experiments. Namely, recall the graphs, X^{p,m}, with p prime ≡ 1 (mod 4) and m > 1 and relatively prime to p from [LPS88] (also in [Mar87]; see [Bie89] for a complete discussion of general m), which are quotients of trees generated by quaternions of norm p. We also recall the graphs, Y^{p,q} for q prime ≡ 1 (mod 4), which are quotients of X^{p,q} and have a particularly simple description: the vertices of Y^{p,q} is the affine line in F_{q}, the finite field of q elements, and quaternions of norm p acting on the affine line as Mobius transformations. These graphs have ρ = max(λ_{2}, −λ_{n}) ≤ 2\sqrt{p − 1}. Each Y^{p,q} is covered by X^{p,q}, and each X^{p,q} is covered by X^{p,qr} for any integer r. Furthermore the number of vertices of X^{p,q} tends to infinity for fixed p as q tends to infinity.

7 Fiber Products and Numerical Calculations

The notions of various types of graph products abound in the literature; for many of these products the spectrum is easily written in terms of the spectra of the terms of the product. One product where this is not the case, and which is not usually mentioned in spectral theory is the fiber product, G_{1} ×_{G} G_{2} of two graphs G_{1}, G_{2} lying above G (see the appendix for its definition). We are interested in the case that G = B_{d}; i.e. G_{i} are d-regular directed graphs given with a proper d-coloring of the edges. Then the fiber product, G_{1} ×_{B_{d}} G_{2}, is a d-regular graph, which is the same as one of the standard graph products except that we keep only edge pairs of the same color. We remak that all graphs are graphs over B_{1}, and the fiber product ×_{B_{1}} is one of the stardard products, namely that which takes graphs with adjacency matrices A_{1}, A_{2} and produces one with adjacency matrix A_{1} × A_{2} (and whose spectrum is therefore the pointwise product of the spectrum of A_{1} and A_{2}).

The fiber product G_{1} ×_{B_{d}} G_{2} has certain interesting properties. The first is that it takes two d-regular graphs and produces a larger d-regular graph; it suggests new graphs and stands a chance of being a building block for graphs with, say, small second eigenvalue. Secondly it enables to give a concise description of certain graphs, which is useful in, say, running numerical experiments on them and other “practical” matters. Thirdly when we twist the fibration (i.e. change the coloring) of, say, G_{2}, we get different graphs. We give a numerical example of one twisting which has a somewhat surprizingly small second eigenvalue.

The graphs X^{p,q}, Y^{p,q} are undirected graphs of degree p + 1, coming from Cayley graphs with generators g_{1}, g_{1}^{−1}, …, g_{s}^{−1} with s = (p + 1)/2; they should therefore be viewed as graphs over W_{s} (see section 5.4). The Chinese Remainder Theorem and the Hasse principle (i.e. Strong approximation, see [Kne66], or [LPS88] for another proof of surjectivity) easily show that

X^{p,q_{1}q_{2}} = X^{p,q_{1}} ×_{s} X^{p,q_{2}}

for q_{1}, q_{2} relatively prime, where we abbreviate ×_{W_{s}} by ×_{s}. This is useful in constructing more simple examples of graphs of this type— aside from Y^{p,q}, which are quite simple to describe, so are their fiber products

Y^{p,q_{1}} ×_{s} ⋯ ×_{s} Y^{p,q_{r}}

for distinct q_{1}, …, q_{r}. That they also have ρ ≤ 2\sqrt{d − 1} follows from the fact that they are covered by X^{p,q_{1}···q_{r}}.

Consider graphs of the form Y^{p,q_{1}} ×_{s} Y^{p,q_{2}}. If one changes the fibration π_{2}: Y^{p,q_{2}} → W_{s} one might wonder what happens to the eigenvalues. In particular, one might expect that having ρ ≤ 2\sqrt{d − 1} is a delicate property, and that tampering with the fibration destroys this property. Numerical experiments show that this is not generally the case, and in fact ρ often decreases when the fibration is changed(!).

Given a cover G of W_{s}, with a fixed covering map π, and a cover σ: W_{s} → W_{s}, we write G_{σ} for the cover (G, σ ∘ π); we call G_{σ} a twisting of G. Given two graphs G_{1}, G_{2} over W_{s}, a twisted product is any fiber product of twisting of G_{1}, G_{2}. Clearly any such twisted product is isomorphic to a twisted product with G_{1} untwisted.

We first consider all the possible twisted products of Y^{5,q_{1}} with Y^{5,q_{2}}, Y^{5,q_{1}} ×_{3} Y_{σ}^{5,q_{2}} for appropriate σ. In choosing σ we note that there are 3 “orientations” of the half-loops to choose and a permutation of {1, 2, 3} to choose, for a total of 48 possible σ’s. Also the Y^{5,q} involve choosing a square root of −1 modulo q, which introduces more possibilities. We claim that there are really only two different graphs that one can generate. We give a table of the largest eigenvalues in absolute value for the two graphs (see table 1).

q_{1} = q_{2} = λ(Y^{5,q_{1}} × Y^{5,q_{2}}) λ(Y^{5,q_{1}} × Y_{σ}^{5,q_{2}}) \binom{5}{q_{1}} \binom{5}{q_{2}} \binom{q_{1}}{q_{2}} n
13 17 −4.3728327  −4.3083943  −1 −1 1 252
13 29 4.3294429  −4.2662239  −1 1 1 420
13 37 4.3854430  4.8793826  −1 −1 −1 532
13 41 −4.3929501  −4.4925255  −1 1 −1 558
13 53 4.4497068  −4.3914762  −1 −1 1 756
13 61 4.4647824  4.4189172  −1 1 1 868
17 29 −4.4442100  4.3346764  −1 1 −1 540
17 37 −4.3804530  4.4278100  −1 −1 −1 684
17 41 4.4536610  4.3783471  −1 1 −1 756
17 53 4.4497068  −4.3914762  −1 −1 1 972

Table 1: λ of twisted products, n ≤ 1000, p = 5 (2\sqrt{5} = 4.4721359 …).

In this table, n = (q_{1} + 1)(q_{2} + 1) is the number of vertices of the graph, λ is the second largest eigenvalue in absolute value, the λ’s are truncated (not rounded) to 7 places (with error < 10^{−7}), and σ is any orientation preseving map on B_{3} which fixes one edge and transposes the other two. We also warn the reader that these values were generated with a randomized algorithm, so that their correctness is not guarenteed; one can say, however, that these numbers are lower bounds for the second eigenvalue and are very unlikely to be incorrect. Similar remarks about accuracy and correctness hold for all of the tables given here.

In the above table we give the Legendre symbols of the primes involved, in case the reader can spot any patterns. We include some more values, in table 2. This includes a few q_{1} = 29 values; it includes q_{1} = 13 and q_{2} ≤ 157, q_{2} = 157 being the first point at which the Legendre symbol \binom{q_{1}}{q_{2}} does not determine whether or not the twist has a smaller second eigenvalue (the author knows of no reason for this bizarre behavior for smaller values of q_{2}); finally we include for q_{1} = 13, 17 all other q_{2} < 300 such that the twist improves the second eigenvalue. The data also suggests that as the number of vertices increases examples of where twisting helps occur less often. We also note that Y^{5,173} has so poor a second eigenvalue that it persists in its lifting to its products with Y^{5,13}, Y^{5,17} and their twists.

To explain why there are only two graphs generated, we note the following symmetries. Any automorphism, ϕ, of the standard quaternion algebra mod q, H_{q}, is given as an inner automorphism, ϕ_{a}(x) = axa^{−1} for some a ∈ H_{q} (by the Noether-Skolem theorem, see [Pie82,

q_{1} = q_{2} = λ(Y^{5,q_{1}} × Y^{5,q_{2}}) λ(Y^{5,q_{1}} × Y_{σ}^{5,q_{2}}) \binom{5}{q_{1}} \binom{5}{q_{2}} \binom{q_{1}}{q_{2}} n
29 37 4.4530135  4.4328406  1 −1 −1 1140
29 41 −4.4126792  4.5059911  1 1 −1 1260
29 53 −4.4174373  −4.6631110  1 −1 1 1620
13 73 4.4081475  4.4853949  −1 −1 −1 1036
13 89 −4.4391579  −4.4967407  −1 1 −1 1260
13 97 −4.4142135  −4.4493451  −1 −1 −1 1372
13 101 4.4459922  −4.4088410  −1 1 1 1428
13 109 −4.3828926  −4.4246632  −1 1 −1 1540
13 113 4.4610164  4.4536431  −1 −1 1 1596
13 137 4.4511993  −4.4723840  −1 −1 −1 1932
13 149 −4.3981705  −4.4819878  −1 1 −1 2100
13 157 4.4594115  −4.5209753  −1 −1 1 2212
13 173 −4.4533279  −4.4533279  −1 −1 1 2436
13 257 4.4557300  4.4477234  −1 −1 1 3612
17 61 −4.4163100  4.3948404  −1 1 −1 1116
17 109 4.4519048  −4.4417525  −1 1 −1 1980
17 173 −4.4533279  −4.4533279  −1 −1 −1 3132
17 241 −4.4700880  4.4620771  −1 1 −1 4356

Table 2: More λ of twisted products, p = 5 (2\sqrt{5} = 4.4721359 …).

Wei74], or the reader can check all the relevant cases by hand). Recall that Y^{p,q}’s edges correspond to the set of quaternions, coming in conjugate pairs, E_{p} = \{α ∈ H | α\overline{α} = p, α ≡ 1 (mod 2)} (reduced modulo q). Let a ∈ H_{q} be such that ϕ_{a} maps E_{p} (i.e. its image reduced modulo q) to itself. Then a determines a twisting, Y_{a}^{p,q}, of Y^{p,q}, via ϕ_{a}’s twisting of E_{p}.

Proposition 7.1 Y_{a}^{p,q} is W_{s}-isomorphic to Y^{p,q}. For any q′ we have Y^{p,q′} ×_{s} Y_{a}^{p,q} is isomorphic (over W_{s}) to Y^{p,q′} ×_{s} Y^{p,q}.

Proof The first isomorphism is given by the map on affine space mod q, x ↦ ãx, where ã is the Möbius transformation corresponding to a. The second statement follows from the first.

□

There are 24 automorphisms of H_{q} onto itself which map E_{p} to itself, such as (i, j, k) ↦ (j, k, i), ↦ (−i, −j, k), ↦ (i, k, −j), etc. Hence of the 48 twists of B_{3}, we get only two conceivably non-isomorphic graphs.

In the above we are assuming that we fix a square root, μ_{q} of −1 modulo q, which gives us a bijection ν: H_{q} → PGL(2, q) from which we obtain Y^{p,q}. Using −μ_{q} instead of μ_{q} gives rise to a new bijection, ν̃ and new graph Ỹ^{p,q}. But the new graph is W_{s} isomorphic to Y_{a}^{p,q} where a comes from the automorphism ν^{−1}ν̃. So this process does not generate any new graphs.

The above table gives some examples of where the twisted product has smaller eigenvalue than the original product. The author does not have a simple interpretation for the arithmetic meaning of the twisted product, and the fact that they sometimes have ρ > 2\sqrt{5} (as shown in the table) suggests that they may not have such an interpretation.

We compare these eigenvalues to that of the Y^{5,q}’s and to random 6 regular graphs. Table 3 gives a list of eigenvalues of Y^{5,q} for q less than around 1000. To compare these eigenvalues

\begin{matrix}q = & λ & q = & λ & q = & λ & q = & λ \\ 13 & 3. & 5615528 & 229 & −4. & 3969876 & 457 & 4. & 4213551 & 757 & 4. & 3259582 \\ 17 & −3. & 4641016 & 233 & 4. & 4475483 & 461 & −4. & 4211984 & 761 & 4. & 3729179 \\ 29 & 4. & 1413361 & 241 & 4. & 3539454 & 509 & −4. & 3861114 & 769 & 4. & 4575070 \\ 37 & −4. & 0000000 & 257 & 4. & 3808292 & 521 & −4. & 4404421 & 773 & 4. & 4152562 \\ 41 & −4. & 1563251 & 269 & −4. & 4281440 & 541 & −4. & 4352388 & 797 & 4. & 4625982 \\ 53 & −4. & 1563251 & 277 & −4. & 4506516 & 557 & 4. & 4441941 & 809 & 4. & 3544312 \\ 61 & −4. & 1826214 & 281 & −4. & 4501734 & 569 & −4. & 3864854 & 821 & −4. & 4051259 \\ 73 & 4. & 4081475 & 293 & 4. & 4201881 & 577 & 4. & 4498917 & 829 & −4. & 4249464 \\ 89 & 4. & 2659810 & 313 & −4. & 4431244 & 593 & −4. & 4108744 & 853 & −4. & 4502504 \\ 97 & −4. & 3141549 & 337 & 4. & 4203043 & 601 & −4. & 3554867 & 857 & −4. & 4224954 \\ 101 & 4. & 2488999 & 349 & 4. & 3650758 & 613 & 4. & 4258625 & 877 & −4. & 4608373 \\ 109 & 4. & 2192444 & 353 & 4. & 4570035 & 617 & −4. & 4024326 & 881 & −4. & 4300769 \\ 113 & 4. & 2715228 & 373 & −4. & 3902568 & 641 & 4. & 4542392 & 929 & −4. & 4514668 \\ 137 & 4. & 2254605 & 389 & 4. & 4500992 & 653 & −4. & 4142135 & 937 & 4. & 4080736 \\ 149 & 4. & 3415806 & 397 & 4. & 4501133 & 661 & 4. & 4250915 & 941 & −4. & 4342184 \\ 157 & 4. & 3247905 & 401 & 4. & 4283013 & 673 & −4. & 4005898 & 953 & −4. & 4641787 \\ 173 & −4. & 4533279 & 409 & 4. & 4161747 & 677 & −4. & 4267661 & 977 & −4. & 3878779 \\ 181 & 4. & 4207598 & 421 & 4. & 3893717 & 701 & −4. & 3894433 & 997 & 4. & 4346157 \\ 193 & 4. & 3142952 & 433 & −4. & 3823991 & 709 & 4. & 4448742 & 1009 & −4. & 4239189 \\ 197 & 4. & 3224143 & 449 & 4. & 4021751 & 733 & −4. & 4563859 & 1013 & −4. & 3738233 \end{matrix} Table 3: λ of Y^{5,q} (2^{\sqrt{5}} = 4.4721359 …).

and those of some of their products to random graphs, we sampled 1000 random graphs with a fixed number of vertices, constructed from 3 random permutations, and computed their eigenvalues; here random means picking a random permutation and applying 200 extra random transpositions for good measure, based on the C routine irand48(). This was performed twice for certain small values of vertices (which are = q +1 for small primes q ≡ 1 (mod 4)), to compare random versus the Y^{5,q}. For the twisted products with (q_{1}, q_{2}) being (13, 17) and (13, 29), we did the experiment once. The results are listed in table 4. These results show that the average spectral radius of a random graph tends to be < 2\sqrt{d − 1}; at present, it is

n Smallest λ  10th λ  100th λ  550th λ 10th larg. λ Larg. λ  Avg. |λ|
14 −3.2822140 3.5045810 −3.8625061 −4.3131283 5.2895440 6.0000000 4.3238381
−3.3009647 −3.5196129 −3.8650207 −4.3079389 5.3359077 6.0000000 4.3125449
18 −3.5546727 3.7601589 3.9815828 −4.3569313 5.0594068 6.0000000 4.3550564
−3.4615425 3.7424164 −3.9865187 4.3529906 5.0623906 6.0000000 4.3522898
30 −3.7825486 −3.9959083 4.1471119 4.3921495 4.9160898 −5.1557566 4.3984882
−3.7701586 3.9575758 4.1347205 −4.3796709 4.9616645 6.0000000 4.3995936
38 3.9451714 4.0835724 −4.2027038 −4.4072455 4.8455419 4.9867719 4.4107891
3.9999286 4.0569757 4.1994161 −4.4008422 −4.7870256 −5.0210640 4.4055494
42 3.9708077 −4.0552115 −4.2282914 4.4110506 −4.8076211 6.0000000 4.4214296
−3.9781894 4.0704865 −4.2205221 4.4128289 4.8257627 5.0294567 4.4239522
54 −3.9818649 4.1446522 −4.2665110 −4.4177893 4.7635511 5.0450831 4.4259959
4.0557738 4.1560708 −4.2662609 −4.4189545 4.7904809 4.9765362 4.4328321
252 4.3178301 4.3666513 4.4015240 4.4528272 4.6187277 4.7921238 4.4579061
420 −4.3814378 4.3991200 −4.4227972 4.4577302 4.5681739 4.6886937 4.4622456

Table 4: λ of 1000 random 6-regular graphs (2\sqrt{5} = 4.4721359 …).

only known that the average spectral radius is ≤ 2\sqrt{d − 1} + 2 log d + C for some constant C (and n sufficiently large depending on d) for most graphs (see [Fri88]), and Alon’s conjecture that for fixed d most graphs on n vertices have λ_{2} ≤ 2\sqrt{d − 1} + ϵ(n) with ϵ(n) → 0 as n → ∞ remains unresolved.

As a rule the fiber product Y^{5,q_{1}} ×_{s} Y^{5,q_{2}} has smaller second eigenvalues than Y^{5,q} type graphs with comparable number of nodes. Sometimes the twisted fiber products, such as those with (q_{1}, q_{2}) being (13, 17), (13, 29), (17, 41), are much better than comparable Y^{5,q} graphs. Also, as a rule it seems easy to find 6 regular graphs on q + 1 vertices with smaller second eigenvalue than that of Y^{5,q}, simply by taking enough random graphs, at least when q is small. To beat the fiber products and their twists seems harder, at least in the first two cases. The tables show that at least 10 out of 1000 random graphs sampled beat Y^{5,13}×_{s}Y^{5,17}. In looking for graphs with 252 nodes that beat Y^{5,13} ×_{s} Y_{σ}^{5,17}, a search of 100,000 random graphs yielded only four graphs with ρ < 4.31, three of which beat Y^{5,13} ×_{s} Y_{σ}^{5,17}, which were:

−4.2937558, −4.2989024, 4.3081363, −4.3089338 .

To beat Y^{5,13} ×_{s} Y^{5,29} and its twist, a search was made among over 1,000,000 random graphs for one with ρ < 4.33; none were found. Following a suggestion of Michael Rabin, a heuristic search was made for degree 6 graphs on 420 nodes with ρ < 4.33: a graph was chosen at random, and each for each of 50,000 iterations 100 random transpositions (in total) were applied to the three permuations from which the graph was constructed; and if the new ρ decreased, then the transpostions were left, if not the old graph was kept. Such a search yielded one graph with ρ < 4.33, namely with second eigenvalue

4.3249334,

on the 48,247th iteration (beating Y^{5,13} ×_{s} Y^{5,29}). A repeated experiment yielded no graph with ρ < 4.33 for 50,000 iterations. Several variations of this experiment, allowing a “simulated annealing” type step, and with varied number of transpositions per iteration using 50,000 iterations, again yielded no such graphs. Finally, a heuristic search of the above type was tried starting at Y^{5,13} ×_{s} Y_{σ}^{5,29}, introducing one random transposition at a time, to try to improve the second eigenvalue; many graphs with smaller second eigenvalue were found, one as low as

4.2420110,

whose adjacency matrix differed from that of Y^{5,13} ×_{s} Y_{σ}^{5,29} in 147 rows. We also remark that the lower bound in section 3 does not give a very interesting lower bound; namely numerical calculations show that T_{6,3}, T_{6,4} respectively have valences 3.71899 and 3.94016.

The next smallest possible value of p, p = 13, already has many more possibilities for the twisting. For example, the second eigenvalue of Y^{13,5} ×_{7} Y^{13,17} was computed as −6.8284271. 33,020 random twistings of the product were made, twisting the permutation of the seven pairs and of the orientations. The following lists the smallest eigenvalue found, the 330th smallest, the 3,302th smallest, the median, the 330th largest, and the largest:

6.5429307, −6.6034627, 6.7329552, 6.9476910, −7.3940794, 8.1223408 .

The smallest eigenvalue was attained 33 of the times, and many eigenvalues were repeated around 30 times. This might seem a lot, since 7!2^{7} = 645120, but one has to recall all the symmetries present. The above theorem enables us to twist both Y^{p,q_{1}} and Y^{p,q_{2}} by the 24 automorphism of the quaternion algebra mapping E_{13} to itself; hence, for any twisting σ on q_{2} any twisting ϕ_{a}σϕ_{b} gives us the same graph, with ϕ_{a}, ϕ_{b} as described above. When σ is the identity then this yields only 24 twistings, however if σ is very non-arithmetical this could yield conceivably 24^{2} twistings. Since 645120/24^{2} = 1120, it is not surprizing that out of 33, 020 random twists many of them were repeated approximately 30 times. The twist which gave the smallest value was the one which took {+1, …, +7} to {−1, −5, −4, 7, −2, −6, 3}, the ± indicating orientation, and the quaternions in order being

3 + 2i, 3 + 2j, 3 + 2k, 1 + 2i + 2j + 2k, 1 + 2i + 2j − 2k, 1 + 2i − 2j + 2k, 1 + 2i − 2j − 2k .

Nati Linial has suggested to the author that it would be interesting to compare the isoperimetric properties of the two fiber products with different fibrations. It might be a little ambitious, given current technology, to find the best isoperimetric sets, but one could certainly compare the expansion of sets such as balls of a given radius, etc.

8 Remarks

We gather some remarks and suggestions for further research.

We have studied some graphs numerically by calculating their second eigenvalue. In many applications one is more interested in their isoperimetric properties, such as how good expanders they are and how few edges induced subgraphs have. It would be interesting to see if in the above examples small second eigenvalue is correlated to these properties, either provably or by numerical experiments.

The fiber product deserves more study. One thing one could consider is for a fixed d and n (with dn even), consider the family of all d-regular graphs on n nodes over B_{d}. If one takes the fiber product of all of these graphs, one gets a type of universal graph. Of course, by Galois theory we know such a product will have many connected components and be, for example, a lousy expander. However, perhaps there is some way to choose a subset of such graphs (e.g. a sufficiently fast algorithm, perhaps computing eigenvalues or randomly testing isoperimetric properties), to produce graphs which can be used for certain explicit construction questions. This is an analogue of the Justesen type constructions in coding theory.

From the more abstract point of view, it would be nice to know in what ways covering/Galois theory for graphs can be related to the same for fields. For example, a graph corresponds to a ring and a connected graph corresponds to a field, given the behavior of × in both theories. Is there a natural ring associated to a graph, so that the ring is a field for connected graphs? Can this be done for certain types of graphs, such as Cayley graphs? Is there an analogue for the notion of modules, exact sequences, etc. in graph theory? Given a finite Cayley graph one can, of course, construct a finite group scheme whose group structure is that of the Cayley graph’s underlying group, but then the ring of global functions on the scheme is only a field for the trivial group.

From the point of view of anaylsis, one of the peculiarities of this theory is due to the fact that the measure μ_{1} is supported at only a finite number of points. One could, of course, work with different measures, such as taking μ = μ_{2} = μ_{1} to be Lebesgue measure on the edges. One would then get an eigenvalue theory with an infinite number of eigenvalues, spanning all of L^{2}(G, μ), etc. One would get an infinite number of eigenpairs, and a similar theory of nodal regions, etc., as well as theorems about the growth rate of the eigenvalues (as in the classical case), holds here. One could study graphs in this way.

In particular, some interest in spectral theory for graphs was due to the possibility of distinguishing non-isomorphic graphs via their spectra (which is not generally possible for the classical graph spectum). If we vary the measures μ_{i} in the Rayleigh quotient, even taking them to have, say, bounded non-zero Radon-Nykodim derivative w.r.t. Lebesgue measure, so that the number of eigenvalues would be infinite, a computer could still, presumably, calculate approximations to some finite number of the eigenvalues. To ask a concrete question, fix an integral constant c > 0; given a graph and a sequence of c edges, consider the measure μ which is Lebesgue measure times i + 1 on the i-th edge for i ≤ c, and is ordinary Lebesgue measure elsewhere. Given two non-isomorphic graphs, is there a choice of a sequence of c edges in the first so that for any choice of c edges in the second graph the resulting spectra differ somewhere in the first n^{c} eigenvalues (by a difference computable in polynomial time)?

Finally, as we suggested in section 4, it would be nice to know more about how the eigenfunctions look, e.g. are their vertices with much larger function values than others, what do their nodal regions look like, etc. In particular, is it true that any d-regular graph with sufficiently many vertices, perhaps satisfying some reasonable properties, has the inradius of at least one of the nodal regions of the second eigenvalue larger than a fixed constant?

9 Acknowledgements

The author wishes to thank Peter Sarnak, Leon Karp, Alex Lubotzky, Ehud DeShallit, Nati Linial, Michael Ben-Or, Michael Rabin, and Noam Nissan for interesting and helpful conversations. In particular, the latter Michael suggested trying a heuristic search and/or simulated annealing as an alternative to picking random graphs, and had related suggestions; dicussions with the former Michael about the numerical experiments and the methods used were of great benifit, as well as his talents and help as a UNIX/C hacker (disguised as a theoretician, of course). Peter Sarnak pointed out an error in an earlier version of the paper and the connections with number theory. The author also wishes to thank Avner Friedman (his dad) and Brian Marcus, for teaching the author much of what he knows about, respectively, Laplacians in analysis (and analysis in general for that matter) and Shannon’s theory.

A Mathematical Background

A.1 Shannon’s algorithm and VLG’s

We recall the Perron-Frobenious theorem. Let A be a non-negative square matrix, whose associated (weighted) graph G_{A}, is strongly connected. Then there is a positive eigenvector, v_{1}, unique up to scalar; let λ_{1} > 0 be its eigenvalue. Then all other eigenvalues are ≤ λ_{1} in absolute value. If A is aperiodic, i.e. A^{n} is positive for some positive n (i.e. the GCD of all cycles in G_{A} is 1), then λ_{1} is strictly larger than all other eigenvalues in absolute value. We shall call λ_{1}(A) the (average) valence of A; its base 2 logarithm is known as A’s capacity. If v is any non-negative vector with Av ≤ cv for a scalar c, then c ≥ λ_{1}, with strict inequality if(f) Av is strictly less than cv in at least one coordinate; similarly with ≤ and ≥ reversed.

If A is a matrix which is non-negative away from the diagonal, G_{A} still being strongly connected, then since A + Ir is non-negative for sufficiently large r, A still has a unique positive eigenvector, v_{1}. We again call λ_{1}(A) the valence, however λ_{1} need not be postive, and even if it is positive it need not be the largest eigenvalue in absolute value.

If G is the nodal region of some (say Dirichlet) eigenfunction (of a larger graph), then A_{0}(G)’s unique positive eigenvector is given by the restriction of the eigenfunction to G. Hence the first Dirichlet eigenvalue of G is the valence of A_{0}(G) in the above sense.

For an aperiodic 0-1 matrix, A, the valence and/or capacity measures the number of walks of length k in G_{A} for large k. Ditto if A has arbitrary non-negative entries, as long as we weight the walks by the product of the edge weights. A natural generalization of this is to variable length graphs, abbreviated VLG’s. A VLG is a graph G = (V, E) along with a positive integral length, ℓ(e), for each e ∈ E. If W (k) denotes the number of walks in G of length ≤ k, length being the sum of the length of the edges, then the valence of G, λ_{1}(G), is defined to be the limit of W (k)^{1/k} as k → ∞; we consider walks of length ≤ k instead of = k to avoid the problems when the GCD of the lengths are > 1, and to facilitate the definition with arbitrary positive edge lengths.

Shannon’s algorithm (see [SW49], chaper 1, section 1) for computing the valence (or capacity) is as follows: let Z_{G} be the matrix whose i, j entry is 0 if (i, j) ∉ E and z^{ℓ} where ℓ is the length of (i, j) otherwise, with z a formal parameter. Then λ_{1}(G) is the reciprocal of the smallest real root of

det(I − Z_{G}) = 0.

More generally, if G has multiple edges and/or positive edge weights associated with the edges, then for each edge of length ℓ and weight w we include a wz^{ℓ} term in Z_{G} and the above algorithm yields the valence of G, generalized in the obvious way. It is easy to see that the notion of valence and algorithm generalize for graphs with arbitrary positive edge lengths and with possibly an infinite number of edges (but finite vertex set!).

Aside from arising naturally in information theory (e.g. Shannon’s telegraph example), VLG’s often give simple ways of working with the capacities of ordinary graphs (see [AFKM86]). Namely, given a graph G = (V, E) and a subset V′ ⊂ V, the realization of G with vertex set V′ is the graph G′ = (V′, E′) where E′ consists of the set of walks starting and ending in V′ which traverse no V′ vertices except at the beginning and end. Each E′ edge comes with a weight and length, depending on the weights and lengths of G’s edges, in the obvious way. It is not hard to see that G′ and G have the same capacity. Typically G′ will have an infinite number of edges; this is always the case when the induced subgraph of G on V − V′ contains a cycle (assuming the G is strongly connected).

In the case when V′ consists of a single vertex, v, Z_{G′} consists of a single entry, which is a power series, P_{v}^{G}(z), representing the number of walks from v to itself which don’t pass through v in the middle; the z^{k} coefficient grows like the valence of the valence of the induced subgraph of G on V − {v}. Shannon’s algorithm implies that if G_{1}, G_{2} are two strongly connected graphs, v_{1}, v_{2} vertices of the graphs, and the number of walks from v_{1} to itself of a given length is ≥ those of v_{2} to itself, then λ_{1}(G_{1}) ≥ λ_{1}(G_{2}); furthermore strict inequality holds iff the number of walks of some length from v_{1} to itself is strictly greater than those of v_{2} to itself.

A.2 Eigenvalue Comparison Theory

Here we give the proof of theorems 2.3 and 2.4. The proofs are the same as in the classical case, which can be found in [CH53, Gar66]. Proof (of theorem 2.3.) The max-min principle says that

λ_{k}(G) = max_{dim(V)=k−1} min_{f∈V^{⊥}} R(f),

with V taken over all subspaces V of the relevant function space H′ of H = H(G) (e.g. H_{0} for the Dirichlet eigenvalues, H for the Neumann eigenvalues), and ⊥ taken in the μ_{1} inner product. The min-max principle says that

λ_{k}(G) = min_{|F |=f} max_{f∈F} R(f),

where the max is taken over all subsets F of k mutually perpendicular non-zero vectors. Furthermore, equality holds for f in the above equations if and only if f is an eigenfunction. Both principles are easy to check.

If f is a first eigenfunction (for some connected graph and some boundary conditions), then the edgewise linear function f̃ whose values on the interior vertices are those of |f| has a Rayleigh quotient ≤ that of f, with strict inequality if there is an edge joining two interior vertices with f values of opposite sign. Furthermore, f̃ cannot vanish on any interior vertices, for if it does so on a vertex, v, we can assume that it does not vanish on a neighbor of v, and then the function f + ϵχ_{v}, where χ_{v} is the characteristic function of v, has smaller Rayleigh quotient for sufficiently small, positive ϵ. Hence f̃ and thus f never vanishes at an interior vertex, and so f’s values at all the interior vertices are all positive or all negative.

No two functions with a strict sign on interior vertices can be orthogonal. Thus the first eigenvalue has multiplicity one, and any other eigenfunction has positive and negative values on the interior vertices.

The fact that an eigenfunction restricted to a nodal region is an eigenfunction of that region with appropriate boundary conditions follows by inspecting the corresponding Laplacians. The fact that is the first eigenfunction follows from the fact that it has a sign on the interior vertices.

The next statement, that ⊆ implies ≤ for eigenvalues follows by applying the min-max principle to G_{2}, with F being the eigenfunctions for G_{1} extended by zero. The proof of strict inequality for the first eigenvalue given strict containment follows from the fact that equality in the min-max principle can only hold for f being an eigenfunction, and yet the first eigenfunction is necessarily edgewise linear and has a strict sign on its interior vertices.

Comparing Dirichlet and Neumann eigenfunctions follows from the min-max principle applied to the Neumann problem (i.e. to H as opposed to H_{0}) as in the last paragraph. For strict inequality with the first eigenvalue, note that along any boundary edge a Neumann eigenfunction must be constant. On the other hand a Dirichlet eigenfunction is zero on a boundary vertex and has a strict sign at the connecting interior vertex. So equality cannot hold in the min-max principle unless the first Dirichlet eigenfunction is a Neumann eigenfunction, which can only happen if there is no boundary; on the other hand, when there is no boudary the two clearly agree.

The statement about changing |a_{w}−1|, the edge lengths, or adding edges, follows from the fact that increasing them does not decrease the Rayleigh quotient evaluated at any function.

The statement about Dirichlet induced eigenvalues of disjointly contained G_{i}’s in G follows from the min-max principle. The statement about Neumann induced follows from the fact that if in the integral ∫ |∇f|^{2} dμ_{2} we allow f to be discontinuous over a discrete set of points, S, and do not integrate through these points, then the Rayleigh quotient does not increase and the class of functions considered is not decreased; when S is taken to be the boundary of the G_{i}’s this yields the desired statement.

□

Proof (of theorem 2.4.) Consider a k-th eigenfunction, with eigenvalue ν_{k}; we claim that there cannot exist k interior disjoint subgraphs, G_{1}, …, G_{k}, such that each G_{i} contains a nodal region and G_{1} contains a nodal region, H, such that at least one boundary point of H lies in the interior of G_{1}. For if so, then f_{i}, the first Dirichlet induced eigenfunction of G_{i}, has Rayleigh quotient ≤ ν_{k} for all i and < ν_{k} for i = 1, by theorem 2.3. But clearly there exists a linear combination f = a_{1}f_{1} + ⋯ + a_{k}f_{k} of the f_{i} such that a_{1} ≠ 0 and f is orthogonal to the first k − 1 eigenfunctions. An easy calculation then shows that the Rayleigh quotient of f is < ν_{k}, which is impossible.

The theorem now easily follows. For example, if there are ≥ k + 1 nodal regions and two of them, H, H′, meet at a non-vertex point, then taking G_{1} = H ∪ H′ and G_{2}, …, G_{k} any other nodal regions yields a contradiction as above. Similarly, if G_{1} is the union of the nodal regions meeting at one vertex, and if there are ≥ k − 1 other nodal regions, again we get a contradiction.

□

References

[AFKM86] R. Adler, J. Friedman, B. Kitchens, and B. Marcus. State splitting for variable length graphs. IEEE Transactions on Information Theory, 32(1):108–115, January 1986.

[AG81] D. Angluin and A. Gardiner. Finite common coverings of pairs of regular graphs. J. Comb. Thy., Series B, 30:184–187, 1981.

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

[Bie89] F. Bien. Constructions of telephone networks by group represenatations. Transactions of the A. M. S., 36(1):3–22, 1989.

[Bro86] R. Brooks. The spectral geometry of a tower of coverings. J. Differential Geometry, 23:97–107, 1986.

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

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

[CH53] R. Courant and D. Hilbert. Methods of Mathematica Physics, Vol. I. Interscience Publishers, New York, 1953. Chaper VI, sections 1,2,4.

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

[DD89] W. Dicks and M.J. Dunwoody. Groups Acting on Graphs. Cambridge University Press, Cambridge, 1989.

[Dod84] J. Dodziuk. Difference equations, isoperimetric inequality and transience of certain random walks. Transactions of the A.M.S., 284(2):787–794, 1984.

[Fri69] A. Friedman. Partial Differential Equations. Holt, Rinehart, and Winston, New York, 1969.

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

[Fri91] J. Friedman. The spectra of infinite hypertrees. SIAM J. on Computing, 1991.

[Gar66] P. Garabedian. Partial Differential Equations. Chelsea, New York, 1966.

[GT83] D. Gilbarg and N. Trudinger. Elliptic Partial Differential Equations of Second Order. Springer-Verlag, New York, 2nd edition, 1983.

[GT87] J. Gross and T. Tucker. Topological Graph Theory. Interscience, John Wiley and Sons, New York, 1987.

[Iha66] Y. Ihara. Discrete subgroups of PL(2, k_{℘}). In Proceedings of Symposia in Pure Mathematics, Volume IX: Algebraic Groups and Discontinuous Subgroups, pages 272–278, 1966.

[Joh90] D.L. Johnson. Presentations of Groups. Cambridge University Press, Cambridge, England, 1990.

[Kne66] M. Knesser. Strong approximation. In Proceedings of Symposia in Pure Mathematics, Volume IX: Algebraic Groups and Discontinuous Subgroups, pages 187– 196, 1966.

[Lei82] F.T. Leighton. Finite common coverings of graphs. J. Comb. Thy., Series B, 33:239–244, 1982.

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

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

[McK81] B. McKay. The expected eigenvalue distribution of a large regular graph. Lin. Alg. Appl., 40:203–216, 1981.

[MKS66] W. Magnus, A. Karras, and D. Solitar. Combinatorial Group Theory. Interscience, John Wiley and Sons, New York, 1966.

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

[Nil91] A. Nilli (pseudonym, N. Alon). A note on the second eigenvalue. Discrete Math., 1991.

[Pie82] R.S. Pierce. Associative Algebras. Springer-Verlag, New York, 1982.

[Sar] P. Sarnak. Number theoretic graphs. preprint.

[Ser80] J.P. Serre. Trees. Springer-Verlag, New York, 1980.

[SW49] Claude E. Shannon and Warren Weaver. The Mathematical Theory of Communication. University of Illinois Press, 1971/1949.

[Wei74] André Weil. Basic Number Theory. Springer-Verlag, New York, 1974.