Wave Equations for Graphs and The Edge-based Laplacian

Joel Friedman^{∗}  Jean-Pierre Tillich^{†}

May 10, 2002

Abstract

In this paper we develop a wave equation for graphs that has many of the properties of the classical Laplacian wave equation. This wave equation is based on a type of graph Laplacian we call the “edge-based” Laplacian. We give some applications of this wave equation to eigenvalue/geometry inequalities on graphs.

1 Introduction

The main goal of this paper is to develop a “wave equation” for graphs that is very similar to the wave equation u_{tt} = Δu in analysis. Whenever this type of wave equation is involved in a result in analysis, our graph theoretic wave equation seems likely to provide the tool to link the result in analysis to an analogous result in graph theory.

Traditional graph theory defines a Laplacian, Δ, as an operator on functions on the vertices. This gives rise to a wave equation u_{tt} = −Δu (since graph theory Laplacians are positive semidefinite). However, this wave equation fails to have a “finite speed of wave propagation.” In other words, if u = u(x, t) is a solution, we may have u(x, 0) = 0 for all vertices x within a distance d > 0 to a fixed vertex, x_{0}, without having u(x_{0}, ϵ) vanishing for any ϵ > 0. As such, this graph theoretic wave equation cannot link most results in analysis involving the wave equation to a graph theoretic analogue.

In this paper we study what appears to be a new type of wave equation on graphs. This wave equation (1) involves a reasonable analogue of u_{tt} = Δu in analysis, (2) have “finite speed of wave propagation” and many other basic properties shared by its analysis counterpart, and (3) seems to be a good vehicle for translating results in analysis to those in graph theory, and vice versa. This wave equation cannot be expressed in the language of traditional graph theory; it requires some of the notions of “calculus on graphs” in [FT99]. This wave equation does, however, have a simple physical interpretation— namely, the edges are taut strings, fused together at the vertices. And in fact, the type of Laplacian we use has appeared in the physics literature as the “limiting case” of a “quantum wire” (see [Hur00, RS01, KZ01] for example); but our type of development of the wave equation and its applications to graph theory seem to have escaped the interest of physicists.

∗Departments of Computer Science and Mathematics, University of British Columbia, Vancouver, BC V6T 1Z4 (V6T 1Z2 for Mathematics), CANADA. jf@cs.ubc.ca. Research supported in part by an NSERC grant.

†LRI bâtiment 490, Université Paris-Sud, Orsay 91405, FRANCE, tillich@lri.fr. Research supported in part by the INRIA and the CCETT.

A second goal of this paper is to point out that whereas in analysis there is really one fundamental Rayleigh quotient, heat equation, and wave equation, in graph theory there are always two. These two fundamental types for an equation or concept result from the fact that graph theory involves two different volume measures. So while in analysis there is usually one fundamental, top (space) dimension volume, in graph theory one has a “vertex-based” measure, V, (a type of vertex counting measure) and an “edge-based” measure, E (essentially Lebesgue measure on edges viewed as real intervals) (see below and section 2 for details); both V, E seem to play a volume measure type of role. So we get a “vertex-based” Rayleigh quotient, heat equation, wave equation, etc. and their “edge-based” counterpart. (We can also formed “mixed” equations and concepts from these two pure types, as well as vary coefficients, add lower order terms, etc.) However, sometimes it turns out that one of the two types of an equation or concept is less interesting. This definitely seems to be the case in the wave equation, where the vertex-based equation does not have finite propagation speed.

A third goal of this paper is to give some examples of how to translate results in analysis to graphs and vice versa using the edge-based Laplacian (including the wave equation). As an example, we give a simple proof of a relation between distances of sets, their sizes, and the first non-zero edge-based eigenvalue; our result can be better (or worse) than that of Chung-Faber-Manteuffel; our proof also works in analysis, and rederives the results in [FT] with a simpler proof. As another example, we show that the optimal generalized Alon-Milman type bound is essentially achieved by a generalized Chung-Faber-Manteuffel bound derived by Chung-Grigor’yan-Yau. We briefly describe how to convert graph theoretic results into analysis results. The results in analysis turn out to be independent of any discussion of edge-based Laplacians, and hence appear as a short, separate article, [FT] (especially for analysts who wish to learn as little graph theory as possible).

In this paper we at times restrict ourselves to finite graphs; at other times we insist that the graphs be locally finite, i.e. that each vertex meets only finitely many edges; finally, some discussion is valid for arbitrary graphs. We will indicate at the beginning of each section and/or subsection when assumptions are made on the graphs therein.

The rest of this introduction, aside from closing remarks, is devoted to giving an informal overview of the simplest form of our wave equation. If this overview seems cryptic, the reader may wish to consult [FT99] or section 2 of this paper.

Let G = (V, E) be a graph. Let G be its geometric realization, i.e. the metric space consisting of V with a real interval of length 1 joining u and v “glued in” for edge {u, v}. Let V be the vertex counting measure, and E be Lebesgue measure on the edges. Then the (positive semidefinite) Laplacian, as in [FT99], takes a function, f, and returns an “integrating factor” (essentially a measure, see section 2),

Δf = (Δ_{V} f) dV + (Δ_{E}f) dE

where Δ_{E} is minus the usual real Laplacian (i.e. second derivative), and Δ_{V} is essentially a sum of normal derivates along edges incident with each vertex. It therefore makes no sense to write a wave equation^{1}

u_{tt} = −Δu,

for the left-hand-side should be a function, and the right-hand-side an integrating factor.

The vertex-based wave equation is the equation

u_{tt} dV = −Δu.

This means that Δ_{E}u = 0, and so u is “edgewise linear” (i.e. a linear function when restricted to any edge). For such a u, Δ_{V} u coincides with the traditional graph theoretic Laplacian, and we recover the wave equation based on traditional graph theory.

The edge-based wave equation is the equation

u_{tt} dE = −Δu,

or Δ_{V} u = 0 and u_{tt} = −Δ_{E}u. This equation has wave propagation speed 1, and has many other properties befitting a wave equation.

When using an edge-based concept, one may speak of Laplacian eigenvalues. In this case one is referring to the set Λ_{E} of λ with Δ_{E}f = λf and Δ_{V} f = 0. However, traditional graph theory deals with Λ_{V}, defined analogously. Fortunately, it is easy to relate the two notions of eigenvalues, assuming we “normalize” the Laplacian Δ_{V} (see section 3). Namely, assuming Δ_{V} is normalized and our graph has all edge lengths one, we have

λ ∈ Λ̃_{E} ⇔ (1 − cos \sqrt{λ}) ∈ Λ_{V}

with Λ̃_{E} being Λ_{E} with some “less interesting” eigenvalues (certain squares of multiples of π) discarded. Λ_{V} is a finite set of values between 0 and 2, and Λ_{E} is an infinite set of non-negative values (whose square roots are periodic, and whose values satisfy a one-dimensional Weyl’s asymptotic law).

1Recall that the minus sign appears in the wave equation since the Laplacian is positive semidefinite.

In this paper we will mildly generalize this setup, allowing for edges of variable “length” and “weight,” and vertices of various “weight.”

The rest of this paper is organized as follows. In section 2 we review some notions from the calculus on graphs of [FT99]. In section 3 we discuss the edge-based eigenfunction theory; it closely resembles standard eigenfunction theory. In section 4 we discuss the wave equation and its basic properties. In section 5 we give some applications of the edge-based Laplacian and the wave equation.

2 Calculus on Graphs

2.1 The Setup

We use a similar setting as in [Fri93], and we recall this setting here. Let G = (V, E) be a graph (undirected), such that with each edge, e ∈ E, we have associated a length, ℓ_{e} > 0. We form the geometric realization, G, of G, which is the metric space consisting of V and a closed interval of length ℓ_{e} from u to v for each edge e = {u, v}. When there is no confusion, we identify a v ∈ V with its corresponding point in G and identify an e ∈ E with its corresponding closed interval in G. By an edge interior we mean the interior of an edge in G.

Definition 2.1 The boundary, ∂G, of a graph, G, is simply a specified subset of its vertices. By the interior of G, denoted G^{o}, we mean G \ ∂G; similarly the interior vertices, denoted V^{o}, we mean V \ ∂G. We say that ∂G is separated if each boundary vertex is incident upon exactly one edge.

Boundary separation is a property whose analogue for manifolds is always true. In most practical situations one can assume that the boundary is separated.

Convention 2.2 Unless specified, in this article we assume all graphs have a separated boundary.

In this article we will give “boundary condition” for functions to satisfy at the boundary. Neumann or mixed boundary conditions (see the next section) behave bizarrely unless the boundary is separated^{2}.

Convention 2.3 By a traditional graph we mean an undirected graph G = (V, E). Throughout this article we assume our graphs are always given with (1) lengths associated to each edge, (2) a specified boundary (i.e. a specified subset of vertices). Whenever an edge length is not specified, it is taken to be one. Whenever a boundary is not specified, it is taken to be empty. We refer to the geometric realization, G, of the graph as the graph, when no confusion may arise.

2It is not hard to see that the Neumann condition for a function, f, on a boundary vertex, v, is equivalent to Δ_{V} f = 0 at v (see this section and the next). This is only equivalent to the normal derivative at f vanishing along all boundary edges if v is incident upon only one edge.

An edge e = {u, v} of length, ℓ, is a real interval of length ℓ, and as such has two standard coordinates, one that sets u to 0 and v to ℓ, and the other vice versa. Whenever we speak of a property such as differentiability, we always mean with respect to these standard coordinates.

Definition 2.4 By C^{k}(G) (respectively C^{k}(G \V)), the set of k-times continuously differentiable functions on G (respectively G \ V) we mean the set of continuous functions on G (respectively G \ V) whose restriction to each edge interior is k-times uniformly continuously differentiable (as a function on that real interval).

We cannot differentiate functions on G without orienting the edges; however, we can take always take the gradient of a differentiable function as long as we know what is meant by a vector field. Recall that a vector field on an interval is a section of its tangent bundle or, what is the same, a function on the interval with an orientation of the interval, where we identify f plus an orientation with −f with the opposite orientation.

Definition 2.5 By C^{k}(TG), the set of k-times continuously differentiable vector fields on G, we mean those data consisting of a k-times uniformly continuously differentiable vector field on each open interval corresponding to each edge interior.

Notice that a vector field is not defined on at a vertex, rather only on edge interiors.

Definition 2.6 For f ∈ C^{k}(G) we may form, by differentiation, its gradient, ∇f ∈ C^{k−1}(TG). For X ∈ C^{k}(TG) we can form, by differentiation, its calculus divergence, ∇_{calc} · X ∈ C^{k−1}(TG \ V).

Definition 2.7 A subset Ω ⊂ G is of finite type if it lies in the union of finitely many vertices and edges. A function on G is of finite type if its support (i.e. the closure of the set where it does not vanish) is of finite type. We set C_{fn}^{k}(G) to be those elements of C^{k}(G) of finite type; we similarly define C_{fn}^{k}(G \ V) and C_{fn}^{k}(TG).

Definition 2.8 An f ∈ C_{fn}^{k}(G) is said to satisfy the Dirichlet condition if f vanishes on ∂G. We let C_{Dir}^{k}(G) denote the set of such functions.

Definition 2.9 Lip(G) denotes the class of Lipschitz continuous functions on G, i.e. those f ∈ C^{0}(G) whose restriction to each edge interior is uniformly Lipschitz continuous. We similarly define Lip_{fn}(G) and Lip_{Dir}(G).

2.2 Two Volume Measures

In analysis concepts such as Laplacians, Rayleigh quotients, and isoperimetric constants are defined using one volume measure; in calculus on graphs we use two “volume” measures.

Definition 2.10 A vertex measure, V, is a measure supported on V with V(v) > 0 for all v ∈ V. An edge measure, E, is a measure with E(v) = 0 for all v ∈ V and whose restriction to any edge interior, e ∈ E, is Lebesgue measure (viewing the interior as an open interval) times a constant a_{e} > 0.

Traditional graph theory usually works with the traditional vertex and edge measures, V_{T} and E_{T}, given by V_{T}(v) = 1 for all v ∈ V and a_{e} = 1 for all e ∈ E, i.e. E_{T} is just Lebesgue measure at each edge.

Convention 2.11 Henceforth we assume that any graph has associated with it a vertex measure, V, and an edge measure, E. When V is not specified we take it to be V_{T}; similarly, when unspecified we take E to be E_{T}.

In this article we write

∫ f dE  and ∫ f dV

for

∫_{G} f dE  and  ∫_{G} f dV.

2.3 Integrating Factors

In this paper a somewhat formal notion will become extremely important.

Definition 2.12 By an integrating factor on G we mean a formal expression of the form μ = α dV + β dE where α is a function defined (at least) on the vertices of G, and β ∈ C^{0}(G \ V).

The continuity assumption on β is not essential, but it makes things nicer for the following reason. An integrating factor as above determines a linear functional L_{μ}, on C_{Dir}^{0}(G) via

L_{μ} = ∫ fμ = ∫ fα dV + ∫ fβ dE.

We say that two integrating factors μ_{i} = α_{i}(x) dV + β_{i}(x) dE for i = 1, 2 are equal if L_{μ_{i}} are equal; clearly this equality amounts to α_{1} = α_{2} at the interior vertices and β_{1} = β_{2} everywhere on G \ V (since the β_{i} are continuous there).

We will sometimes wish to insist that α_{1} = α_{2} on boundary vertices as well; this corresponds to viewing integrating factors as linear functionals on C^{0}(G). In this case we will speak of boundary inclusive equality.

In the calculus on graphs we have two measures, and thus a need for integrating factors, i.e. the need to mark functions with a dV or dE to remind us how to integrate the function against other functions. For example, we shall soon see that the divergence of a vector field or the Laplacian of a function is an integrating factor. Consequently, any wave or heat equation is most correctly regarded as an equation between integrating factors. (In traditional graph theory, all integrating factors have a vanishing dE component, i.e. β = 0 in the above, and they may be considered as functions on the vertices, i.e. they may be identified with α’s values on the vertices.)

2.4 Regular graphs

In this article when we say that a graph is r-regular, it has a slightly more general meaning than in traditional graph theory where all vertices and edges have weight 1 (in other words E = E_{T} and V = V_{T}).

Here we mean the following

Definition 2.13 We say that a graph G is r-regular if for any v ∈ V^{o}, ρ_{inf}(G) = r, where

ρ(v) = V(v)^{−1} ∑_{e∋v} E(e).

Clearly graphs which are r-regular in the traditional sense, are also regular with our definition. Note that the quantity ρ(v) arises quite naturally when we consider edgewise linear functions, i.e continuous functions whose restriction to each edge is a linear function. For these functions we clearly have

∫_{e} f dE = (f(u) + f(v))E(e)/2

for each edge e = {u, v}. Hence

∫ f dE = ∫ fρ/2 dV,  (2.1)

2.5 The Divergence

The divergence of a vector field and the Laplacian of a function can be defined in terms of concepts that are already fixed, namely a graph (encompassing measures E and V) and the gradient. Interestingly enough, the divergence turns out to be different from the “calculus divergence” described earlier.

Before defining the divergence we record a “divergence theorem” for the calculus divergence.

Let X ∈ C^{1}(TG). For any edge e = {u, v} let X|_{e} denote X restricted to the interior of e and then extended to u and v by continuity. We clearly have

∫_{e} ∇_{calc} · X dE = a_{e}(n_{e,u} · X|_{e}(u) + n_{e,v} · X|_{e}(v)),

where n_{e,u}, n_{e,v} denote outward pointing unit (normal) vectors. Hence we obtain:

Proposition 2.14 For all X ∈ C_{fn}^{1}(G) we have

∫ ∇_{calc} · X dE = ∫ ñ · X dV,  (2.2)

where

(ñ · X)(v) = V(v)^{−1} ∑_{e∋v} a_{e}n_{e,v} · X|_{e}(v).

Let C_{Dir}^{k}(G) denote those functions in C_{fn}^{k}(G) that vanish on the boundary of G.

Definition 2.15 For a vector field, X, its divergence functional is the linear functional L_{X}: C_{Dir}^{∞}(G) → ℝ given by,

L_{X}(g) = −∫ X · ∇g dE.

Proposition 2.16 For any X ∈ C^{1}(TG) and g ∈ C_{Dir}^{∞}(G) we have

L_{X}(g) = ∫ (∇_{calc} · X)g dE − ∫ (ñ · X)g dV,

i.e. the divergence functional of X is represented by (∇_{calc} · X) dE − (ñ · X) dV (viewed as a linear functional via integration).

Proof We substitute Xg for X in equation 2.2, and note that ∇_{calc} · (Xg) = g∇_{calc} · X + X · ∇g.

Definition 2.17 For X ∈ C^{1}(TG) we define its divergence, ∇·X, to be the integrating factor

(∇_{calc} · X)dE − (ñ · X)dV.

If X is edgewise constant, so that ∇_{calc} · X = 0, we will also refer to

−ñ · X

(a function defined only on vertices) as its divergence, and write ∇ · X for it.

We conclude:

Proposition 2.18 For any g ∈ C_{fn}^{1}(G) and X ∈ C_{fn}^{1}(TG) we have

∫_{G}(∇ · X)g + ∫ X · ∇g dE = 0.

To make this look more like analysis we can write this as:

∫_{G\∂G}(∇ · X)g + ∫ X · ∇g dE = ∫_{∂G}(ñ · X)g dV.

2.6 The Laplacian

In graph theory we usually define positive semidefinite Laplacians. So we define

Δf = −∇ · (∇f).

As integrating factors we have

Δf = (Δ_{E}f) dE + (Δ_{V} f) dV,

with Δ_{E}f = −∇_{calc} · ∇f and Δ_{V} f = ñ · ∇f. It is easy to see that:

Proposition 2.19 For all f ∈ C_{fn}^{2}(G) and g ∈ C_{fn}^{1}(G) we have

∫ (Δf)g = ∫ ∇f · ∇g dE.  (2.3)

If also g ∈ C_{fn}^{2}(G) we have

∫ (Δf)g = ∫ (Δg)f.  (2.4)

The link with the traditional graph theoretic Laplacian is as follows:

Proposition 2.20 For f ∈ C_{fn}^{2}(G) which is edgewise linear we have ∇_{calc} · ∇f = 0 and so Δf = ñ · ∇f dV. Viewing Δf as a function on vertices we therefore have:

(Δf)(v) = V(v)^{−1} ∑_{e∼\{u,v\}} a_{e} \frac{f(v) − f(u)}{ℓ_{e}}.  (2.5)

When restricting to edgewise linear functions, it is common (in graph theory) to write Δ as D − A, where D is the diagonal matrix or operator (classically the “degree” matrix) whose v, v entry is:

L(v) = V(v)^{−1} ∑_{e∼{u,v}} a_{e}/ℓ_{e},

where we omit e’s that are self-loops from the summation, and where A is the “adjacency” matrix or operator given by

(Af)(v) = V(v)^{−1} ∑_{e∼{u,v}}(a_{e}/ℓ_{e})f(u),

again omitting self-loops, e.

2.7 Variable Integrals

We shall wish to consider the derivative at t = t_{0} of the function

I(t) = ∫_{S(t)} f(x, t) dE(x),

where t is a real parameter, S(t) is a decreasing family of open subsets of G, and f(x, t) is continuous in x (taking values in G) and differentiable in t (taking values near t_{0}).

For this paper we only need consider S(t) given by the set of points within a distance τ − ct from a fixed set A ⊂ G, with τ fixed and 0 ≤ t_{0} < τ. We will assume S(t) is of finite type for t near t_{0}, and that ∂S(t_{0}) is finite and contains no vertices.

With the above assumptions, the formula for I′(t_{0}) is very easy. We will discuss more general variants of these formulas later. These more general variants are not needed in this paper, but are interesting to consider and compare with the co-area formula and its problems at the vertices as described in [FT99].

Calculus says that that if a, b, c are constants with c > 0, and f = f(x, t): ℝ^{2} → ℝ is continuous in x and differentiable in t, then

\frac{d}{dt} ∫_{a+ct}^{b−ct} f(x, t) dx = −c\{f(a + ct, t) + f(b − ct, t)\} + ∫_{a+ct}^{b−ct} f_{t}(x, t) dx,

where f_{t} is the partial derivative of f in t. If we replace a + ct by a in the above integral, then the f(a + ct, t) drops out, and similarly for b − ct replaced by b.

Summing the above calculus equality over all edges yields the following easy proposition.

Proposition 2.21 Let S(t), f(x, t), t_{0}, I(t) be as above. Then

I′(t_{0}) = − ∑_{(x,e) with x∈∂S(t_{0}),e∋x} f(x, t_{0})ca_{e} + ∫_{S(t_{0})} f_{t}(x, t_{0}) dE(x).  (2.6)

In other words, the above sum is over all boundary points, x, of S(t_{0}), and involves the edge, e, on which x lies.

Finally, we remark that if S(t) does not decrease “linearly” with speed c everywhere, then we simply replace c by the speed at with ∂S(t) moves at x in the summation of any of the above formulas.

We finish this subsection by describing what happens when ∂S(t_{0}) contains vertices. If so, then the left and right derivatives of I(t) at t_{0} will exist but won’t usually be equal. Equation 2.6 will essentially hold, but different (x, e) pairs appear in the sum. So consider pairs (x, e) with x ∈ e ∪ ∂S(t_{0}) (remember we identify an edge with its closed interval in G, so x may be a vertex); we call a pair future active if e’s interior intersected with S(t_{0}) contains an open interval ending at x. In other words, the picture of S(t) near x and along e is changing for t > t_{0} near t_{0} (since S(t) is decreasing in t). We say that a pair (x, e) is past active if either x is not a vertex, or x is a vertex and (x, e) is not future active, see figure below. (Geometrically, since S(t) is decreasing in t, we are saying that for t near t_{0} and at a boundary point, x, the picture of S(t) always changes when x is not a vertex, and when x is a vertex it changes along some edges in the future (t > t_{0}) and other edges in the past (t < t_{0}).)

Summing the calculus formula shows that the right derivative of I at t_{0} exists and equals

I′(t + 0) = − ∑_{(x,e) future active} f(x, t_{0})ca_{e} + ∫_{S(t_{0})} f_{t}(x, t_{0}) dE(x).  (2.7)

Similarly the left derivative is the same, with future active replaced by past active pairs (x, e).

Notice that the notion of “future active” essentially arose in the definition of the area of the boundary of a subset, in [FT99], section 2, in connection with the co-area formula.

3 The Edge-Based Eigenvalues and Eigenfunctions

In this section we discuss some facts about the “edge-based” Laplacian and its eigenpairs, i.e. pairs (f, λ) with Δ_{E}f = λf and Δ_{V} f = 0. Such pairs a crucial to understanding the solutions to the wave equation and invariants associated with it. We concern ourselves with the basic cases at first, later illustrating fancier boundary conditions and mixed edge and vertex Laplacians.

It is worth mentioning that the equations Δ_{E}f = λf and Δ_{V} f = 0 describe the modes associated with a physical object with a metal string for each edge, with strings being fused together at the vertices. For example, if we “pluck” such an object, it would produce tones with the frequencies of \sqrt{λ} with λ ranging over the edge-based eigenvalues (this is seen from considering the wave equation of the next section).

3.1 Basic Existence Theory

Definition 3.1 (f, λ) is an eigenpair for the “edge-based” Laplacian if f ∈ C^{∞}(G) and satisfies Δ_{E}f = λf and Δ_{V} f = 0. We say that f satisfies the Dirichlet condition if f vanishes at all boundary points; the similarly for the Neumann condition, where f’s normal derivatives along its edges evaluated at any boundary point vanish.

Notice that the condition Δ_{E}f = λf implies that f’s restriction to each edge is given by A cos(ωx + B), where A, B are constants, ω = λ^{1/2}, and x represents one of the two standard coordinates on the edge.

The existence of a complete set of eigenpairs for the Laplacian is well understood in analysis for compact domains, and the same techniques carry over to our setting, for finite graphs, with almost no modifications. We only summarize the theory, and refer the reader to [GT83] or [Fri69].

Proposition 3.2 Let G be a finite graph. There exists eigenpairs (f_{i}, λ_{i}) for the edge based Laplacian, such that (1) 0 ≤ λ_{1} ≤ λ_{2} ≤ ⋯, (2) the f_{i} satisfy the Dirichlet condition, (3) the f_{i} form a complete orthonormal basis for L_{Dir}^{2}(G, E), and (4) λ_{i} → ∞. The same statement holds with Dirichlet replaced by Neumann and L_{Dir}^{2}(G, E) replaced by L^{2}(G, E).

Proof Consider the Rayleigh quotient

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

which is certainly defined for f ∈ C^{1}(G). Let u_{1}, u_{2}, ⋯ be a minimizing sequence for R in C_{Dir}^{1}(G), i.e. u_{i} ∈ C_{Dir}^{1}(G) with

R(u_{i}) → inf_{f∈C_{Dir}^{1}(G)} R(f).

We may assume ∫ |u_{i}|^{2} dE = 1, and thus that ∫ |∇u_{i}|^{2} dE are bounded. Let H_{Dir}^{1}(G) be the closure of C_{Dir}^{1}(G) under the norm

∥f∥_{H^{1}}^{2} = ∫ [|∇f|^{2} + |f|^{2}] dE;

H_{Dir}^{1}(G) can also be described with Fourier transforms, or as the set of L^{2} functions with a weak derivative in L^{2}; it is well known to be a separable Hilbert space, therefore having a weakly compact unit ball. Hence by passing to a subsequence we may assume that the u_{i} converge weakly in H^{1} to a u ∈ H_{Dir}^{1}(G).

We claim that the u_{i} are uniformly Hölder continuous of exponent 1/2. To see this let x, y ∈ G be of distance ρ, and fix a path γ of length ρ from x to y. We have

|u_{i}(x) − u_{i}(y)| ≤ ∫_{γ} |∇u_{i}| dE ≤ (∫_{γ} dE)^{1/2} (∫_{γ} |∇u_{i}|^{2} dE)^{1/2} ≤ Cρ^{1/2}∥u_{i}∥_{H^{1}},

where C is the maximum over edges e of a_{e}^{−1/2}. Hence our claim holds, and by Ascoli’s lemma we can pass to a further subsequence and assume that the u_{i} converge uniformly to a u which is Hölder continuous of exponent 1/2; since the u_{i} vanish on the boundary, so does u.

We have (by the uniform convergence and the weak H^{1} convergence)

R(u) ≤ lim inf R(u_{i}),

and so equality must hold and u minimizes R over all of H_{Dir}^{1}(G).

Now we claim that u is our desired eigenfunction, and λ = R(u) its eigenvalue. This is seen by setting λ = R(u) and considering R(u + ϵw) for various w ∈ H_{Dir}^{1}(G) and taking ϵ → 0. We conclude that

∫ ∇u∇w dE = λ∫ uw dE  (3.1)

for all w ∈ H_{Dir}^{1}(G). Now standard estimates for elliptic equations (e.g. lemma 15.4 of [Fri69]) show that in fact u is C^{∞} at all edge interiors, and satisfies

Δ_{E}u = λu.  (3.2)

Hence u’s restriction to any edge is given as A cos(ωx + B) for ω = λ^{1/2}, and A, B are constants depending on e (and which of the two standard coordinates we place on e). Since u is Hölder continuous on G, it is certainly continuous everywhere, including all its vertices. Hence u ∈ C_{Dir}^{∞}(G). Finally, given a vertex, v, let us show that (Δ_{V} u)(v) = 0. From proposition 2.19 we know that

∫ ∇u · ∇w dE = ∫ (Δ_{E}u)w dE + ∫ (Δ_{V} u)w dV
= λ ∫ uw dE + ∫ (Δ_{V} u)w dV

From (3.1) and (3.2) we obtain

∫ (Δ_{V} u)wdV = 0.  (3.3)

We choose w ∈ C_{fn}^{1}(G) in equation 3.1, such that w(v) = 1 and w(v′) = 0 on other vertices and conclude

(Δ_{V} u)(v) = 0.

Letting h → 0 we conclude that u is an “edge-based” Laplacian eigenfunction satisfying the Dirichlet condition, with eigenvalue λ.

Set f_{1} = u and λ_{1} = λ. Now repeat the same argument, except minimizing R over those functions that are orthogonal to f_{1}. With the same argument as before, we find an eigenpair (f_{2}, λ_{2}) with λ_{1} ≤ λ_{2} and f_{1} orthogonal to f_{2}. Now repeat again, minimizing over functions orthogonal to f_{1} and f_{2}. In this way we get a sequence of orthogonal eigenpairs (f_{i}, λ_{i}) with λ_{i} non-decreasing in i.

Next we show that λ_{i} → ∞. If not, then the H^{1} norm of the f_{i} are uniformly bounded, and so the f_{i} are uniformly Hölder continuous, and so a subsequence of the f_{i} converges uniformly to a g. But since the f_{i} are orthogonal, g would be orthogonal to all f_{i} and therefore to itself, so g = 0. This contradicts the uniform convergence of the subsequence of f_{i} to g.

It remains to show that the f_{i} are complete. If the f_{i} are not complete, there is a non-zero g ∈ L_{Dir}^{2}(G) orthogonal to all the f_{i}. By convolving g with smooth approximations to Dirac’s delta function, and modifying it at the vertices, we can find an g_{ϵ} ∈ C_{Dir}^{∞}(G) for any ϵ > 0 with ∥g − g_{ϵ}∥_{L^{2}} ≤ ϵ. Hence for small ϵ the function, h, which is the projection of g_{ϵ} onto the complement of the f_{i}’s, is (1) non-zero, (2) orthogonal to all f_{i}, and (3) lies in H_{Dir}^{1}(G). Now R(h) must upper bound the λ_{i}, by their minimizing property. Hence λ_{i} are bounded, which we know is impossible.

We finish by remarking that the same proof holds for the Neumann condition, except that we begin by working with C^{1}(G) instead of C_{Dir}^{1}(G).

□

The same theorem holds for more general “mixed” boundary conditions. Namely, we consider the condition that a function, f, satisfy the mixed condition

f = 0 on K_{1}, and  (3.4)
ñ · ∇f + σf = 0 on K_{2},  (3.5)

where K_{1}, K_{2} are a partition of ∂G and where σ is non-negative. Then the same theorem and proof hold, provided that we replace C_{Dir}^{1}(G) by

{f ∈ C^{1}(G) | f = 0 on K_{1}},

and replace the Rayleigh quotient, R, by

R̃(f) = \frac{∫ |∇f|^{2} dE + ∫_{K_{2}} σf^{2} dV}{∫ |f|^{2} dE} .  (3.6)

We mention that V does not enter in any essential way into the edge-based eigenvalues. Only E should affect those eigenvalues.

We mention that we can get mixed edge-vertex Laplacians. So consider the Rayleigh quotient:

R(f) = \frac{∫ γ|∇f|^{2} dE}{∫ αf^{2} dV + ∫ βf^{2} dE} ,

with α, β, γ continuous, non-negative and γ differentiable and never vanishing. Its successive minimizers satisfy

−∇ · (γ∇f) = λf(α dV + β dE).  (3.7)

The above theorem gives us a complete eigenbasis for L^{2}(G, μ) with μ = αV +βE. This basis is infinite provided that β is not identically zero.

Finally, we mention that it is easy to modify the above to work for mixed boundary conditions with mixed edge-vertex Laplacians.

3.2 Weyl’s Law

One fundamental result about edge-based eigenvalues that is true for any finite graph is that their growth rate is determined, to first order, by the sum of the lengths of their edges. In analysis the analogous quantity is the volume of the subdomain or manifold, and Weyl’s proof of this fact (see [Wey12]) in analysis immediately carries over here.

For a finite graph, G, let N_{Dir}(λ, G) be the number of Dirichlet edge-based eigenvalues ≤ λ for G, and similarly for N_{Neu}(λ, G).

Proposition 3.3 (Weyl’s Law) Fix a finite graph, G. Let N(λ) be either N_{Dir}(λ, G) or N_{Neu}(λ, G). There is a constant, C, such that

|N(λ) − Lλ^{1/2}/π| ≤ C,

where L is the sum of all the lengths of the edges in the graph.

Proof Consider the graph, G_{1}, where every vertex is a boundary point. Then the edge-based eigenvalues of G_{1} are found by minimizing the same Rayleigh quotient over a more restrictive class of functions. Hence, by the min-max principle, we have

N_{Dir}(λ, G_{1}) ≤ N_{Dir}(λ, G).

Similarly we have

N_{Neu}(λ, G) ≤ N_{Neu}(λ, G_{1}),

for the latter function corresponds to a Rayleigh quotient over the space of functions which needn’t be continuous at any vertex. For similar reasons we have

N_{Dir}(λ, G) ≤ N_{Neu}(λ, G),

the former N corresponding to the same class of functions as the latter except the latter need not vanish at boundary vertices. To summarize, we have shown

N_{Dir}(λ, G_{1}) ≤ N_{Dir}(λ, G) ≤ N_{Neu}(λ, G) ≤ N_{Neu}(λ, G_{1}).

Hence it suffices to prove the proposition for G_{1}.

But the values of the G_{1} eigenfunctions don’t interact across vertices, so

N_{Dir}(λ, G_{1}) = ∑_{e∈E} N_{Dir}(λ, e),

where edges, e, are also viewed as graphs. If e is an edge of length ℓ, its Dirichlet eigenfunctions are f_{n}(x) = sin(nxπ/ℓ) for n = 1, 2, …, with eigenvalues λ_{n} = (nπ/ℓ)^{2}. Hence we have

N_{Dir}(λ, e) = ⌊λ^{1/2}ℓ/π⌋.

It follows that for some constant C > 0,

N_{Dir}(λ, G_{1}) ≥ −C + (λ^{1/2}/π) ∑_{e∈E} ℓ_{e} = −C + Lλ^{1/2}/π.

For similar reasons the result also holds for N_{Neu}(λ, G_{1}), where the eigenfunctions on an edge are f_{n}(x) = cos[(n − 1)xπ/ℓ] for n = 1, 2, …, with eigenvalues λ_{n} = [(n − 1)π/ℓ]^{2}.

□

Again, a similar result holds for mixed boundary conditions. To see this, we shall show that for any fixed mixed boundary condition (as in the end of the previous subsection)

N_{Dir}(λ, G) ≤ N_{mixed}(λ, G) ≤ N_{Neu}(λ, G),

where N_{mixed} counts eigenvalues with a mixed condition. Indeed, N_{Dir} can be viewed as having the same Rayleight quotient, as in equation 3.6, as N_{mixed}, except over a smaller space (i.e. the space of functions vanishing over all of ∂G, not just K_{1}). Furthermore, the Rayleigh quotient for N_{mixed} is no less than that for N_{Neu}, and the space for the former is more restrictive. Hence the claim that N_{Dir} ≤ N_{mixed} ≤ N_{Neu}, and hence the asymptotic law.

To get an asymptotic law for mixed edge-vertex Laplacians (as in equation 3.7), the above arguments show it suffices to consider Dirichlet and Neumann eigenvalues for an edge, e. Partition e into k intervals, I_{1}, … I_{k}, and on a fixed interval, I_{j}, set γ_{max} to be the maximum value of γ there, and β_{min} similarly. The Rayleigh quotient with γ_{max} replacing γ and β_{min} replacing β is never smaller, and so the Dirichlet eigenvalue counting function on I_{j} for the Rayleigh quotient with β and γ is at least

⌊λ^{1/2}|I_{j}|β_{min}/(γ_{max}π)⌋.

We conclude that for any ϵ > 0 we have that the Dirichlet eigenvalue counting function on e is at least

λ^{1/2}(1/π)(−ϵ + ∫_{e} β(x)/γ(x) dx),

where x is a standard coordinate on e. We conclude a similar upper bound for the Neumann eigenvalues, and conclude that N(λ) ∼ λ^{1/2}C/π, where

C = ∑_{e} ∫_{e} β(x)/γ(x) dx.

3.3 A Condition on Edge-Based Eigenfunctions

Proposition 3.4 Let G be a locally finite graph. Let (f, ω) be an edge-based eigenpair for the Laplacian, and let ω = λ^{1/2}. Let v be an interior vertex such that ωℓ_{e} is not a multiple of π for any e incident upon v. Then

∑_{e∼\{v,u\}} a_{e} \frac{f(u) − cos(ωℓ_{e})f(v)}{sin(ωℓ_{e})} = 0.

If the degree of v is infinite, the theorem still holds provided the above sum converges absolutely (and Δ_{V} is understood in the natural way). Proof This is as simple consequence of the fact that if f is an eigenfunction then Δ_{V} f(v) = 0 at any interior vertex. Fix an edge e ∼ {v, u}, and let x be the standard coordinate on e with x(v) = 0 and x(u) = ℓ_{e}. We have f’s restriction to e with coordinate x, f_{e} = f_{e}(x) = A cos(ωx + B) for some A, B. Hence

f(v) = f_{e}(0) = A cos B,

and

f(u) = f_{e}(ℓ_{e}) = A cos B cos(ωℓ_{e}) − A sin B sin(ωℓ_{e}),

and the outward normal derivative of f at v is

f′(0) = −Aω sin B = −ω \frac{f(u) − cos(ωℓ_{e})f(v)}{sin(ωℓ_{e})}.

Since Δ_{V} f = ñ · ∇f at v is V(v)^{−1} times the sum of the above times a_{e}, we conclude the proposition.

□

Using the above proposition one can rather easily determine all the edge-based eigenpairs in terms of the eigenpairs of the “normalized” adjacency matrix of the graph, provided that all edge lengths are equal; the ω’s will turn out to be periodic of period 2π. However, we do not know of such a determination when edge lengths vary; we shall show that a graph with two vertices joined by three edges of varying edge lengths will not have periodic ω’s.

3.4 The Equilength Case

In this subsection we consider a finite graph, G, all of whose edges have length 1 (however the a_{e} can vary). We can similarly deal with any graph whose edge lengths are equal.

For any v ∈ V^{o}, let a_{v} be the sum of the a_{e} over all edges, e, incident with v (these edges, e, may be incident with boundary vertices). We will assume that G is connected with at least one edge, so that a_{v} > 0 for all v. Let Ã be the “normalized” adjacency matrix, which is just the adjacency matrix of section 2, normalized by dividing each row by its corresponding a_{v}. Ã represents a Markov chain iff G has no boundary vertices (and it always represents a Markov chain if we add in the boundary vertices and make them “absorbing” states).

Our main result describes the edge-based eigenvalues in terms of Ã and the number of edges and interior vertices. We state this first, and then prove it in a series of propositions. First we set

ℤ_{≥0} = {0, 1, 2, 3, …},

so that for any τ ∈ ℝ we can write

τ + 2πℤ_{≥0} = {τ, τ + 2π, τ + 4π, …}.

Theorem 3.5 Let G be a connected graph with at least one edge, and let Ã be its normalized adjacency matrix, as above. The edge-based eigenvalues is the multiset sum^{3} of the following sets: for each eigenvalue, λ, of Ã, there is a unique cos^{−1}(λ) ∈ [0, π]; corresponding to this λ we have eigenvalues

cos^{−1}(λ) + 2πℤ_{≥0},  and  2π − cos^{−1}(λ) + 2πℤ_{≥0}.  (3.8)

Additionally, the sets

π + 2πℤ_{≥0},  and  2π + 2πℤ_{≥0}  (3.9)

occur with mutliplicity |E| − |V^{o}|. This means that if |E| − |V^{o}| = −1, i.e. G is a tree without boundary, then we subtract the list in equation 3.9 once from the union over equation 3.8; i.e. nπ for non-negative integer n occurs with mutliplicity one.

Let us mention that if G has separated boundary, then the Neumann condition at a boundary vertex is equivalent to considering that vertex to be an interior vertex. Hence our theorem really also handles the case where we impose a Dirichlet condition on some vertices, and a Neumann condition on the rest, assuming the rest are separated. Proof The proof of this theorem occupies the rest of this section. We prove it in a sequence of proposition. Notice that our proof provides a method for finding a basis for the eigenspaces.

3i.e. if λ occurs five times in the lists below, then its multiplicity is five.

Proposition 3.6 Let ω ∈ ℝ \ (πℤ). Then ω^{2} is a edge-based Dirichlet eigenvalue iff cos ω is an eigenvalue of Ã. If so, ω^{2}’s multiplicity is that of cos ω in Ã, and for each corresponding eigenfunction, f, of Ã (therefore defined on the vertices), we may extend f along each edge (as A cos(ωx + B) for some A, B and standard edge coordinate x) to an edge-based eigenfunction.

Proof If ω ∈ ℝ \ (πℤ) has ω^{2} an edge-based eigenvalue, then by proposition 3.4 we have for each v

∑_{e∼{v,u}} a_{e}f(u) = cos(ω)f(v) ∑_{e∼{v,u}} a_{e}.

In other words, since f is Dirichlet,

Ãf = cos(ω)f,

i.e. cos ω is an eigenvalue of Ã.

Conversely, let cos ω ≠ ±1 be an eigenvalue of Ã with eigenfunction g. We claim that for any fixed e = {u, v}, there is a unique way to extend g to a function along e of the form A cos(B + ωx), where x is the standard coordinate on e with x(v) = 0. Indeed, consider the equations in A, B for fixed g(u), g(v)

g(v) = A cos B  (3.10)
g(u) = A cos(B + ω)  (3.11)

Since

A sin B = \frac{g(u) − g(v) cos ω}{− sin ω} ,

we have that A cos B and A sin B are uniquely determined by g(u), g(v). From what we know of polar coordinates, this means either A = 0 and B is arbitrary, in which case g’s extension along e is by 0 (and g(u) = g(v) = 0), or there is a unique positive A = A_{0} and unique B = B_{0} modulo 2π satisfying the equations, with the only other solution being A = −A_{0} and, modulo 2π, B = B_{0}+π. Since the function A cos(B+ωx) is the same for these solutions, and does have the right value at x = x(v) = 0 and x = x(u) = 1, g can be extended to satisfy Δ_{E}g = ω^{2}g. Also clearly g satisfies the condition in proposition 3.4, which is equalent to Δ_{V} g = 0.

To summarize, we know that ω^{2} is an edge-based eigenvalue for ω ∈ ℝ \ (ℤπ) iff cos ω is an eigenvalue of Ã. We know that the restriction of any Δ_{E} eigenfunction gives a Ã eigenfunction, and we know that (given ω) a Ã eigenfunction g has a unique extension to a Δ_{E} eigenfunction. Hence the multiplicities of ω^{2} in Δ_{E} and cos ω in Ã are equal.

□

The story when ω ∈ πℤ is less elegant. Indeed, there are many edge-based eigenfunctions, f, whose restriction to the vertices vanishes.

Let Y_{ω} be the eigenspace corresponding to the Dirichlet edge-based eigenfunctions with eigenvalue ω^{2},

Y_{ω} = Y_{ω}(G) = {f ∈ C_{Dir}^{∞}(G) | Δ_{E}f = ω^{2}f, Δ_{V} f = 0},

and let Z_{ω} be those elements of Y_{ω} vanishing on all vertices,

Z_{ω} = Z_{ω}(G) = {f ∈ Y_{ω} | f|_{V} = 0}.

We reduce the study of Y_{ω} for ω ∈ πℤ to that of Z_{ω} by the following proposition.

Proposition 3.7 Y_{ω}/Z_{ω} for ω ∈ 2πℤ is one dimensional if ∂G = ∅, and otherwise zero. Similarly for ω ∈ π + 2πℤ, except that we require ∂G = ∅ and that G is bipartite.

Proof If f ∈ Y_{2πn} with n ∈ ℤ, and e = {u, v} is an edge, then f(u) = f(v), since f’s restriction to e is of the form A cos(B + 2πnx). Hence f must be constant on V. This implies that Y_{ω}/Z_{ω} is at most one dimensional, and must be zero if ∂G ≠ ∅. One the other hand, if ∂G = ∅ then the function whose restriction to each edge is cos(ωx) gives a non-zero element of Y_{ω}/Z_{ω}. The case ω = (2n + 1)π is handled similarly.

□

The following two propositions essentially finish our work in this subsection.

Proposition 3.8 For ω > 0 there is a natural isomorphism of Y_{ω} with Y_{ω+2π} which restricts to an isomorphism of Z_{ω} with Z_{ω+2π}. The same is true if ω + 2π is replaced by ω + π, provided that G is bipartite.

Proof If f ∈ Y_{ω}, let ιf be the function whose restriction to e is A cos[B + (2π + ω)x] where A, B are given by f’s restriction to e being A cos(B + ωx). Then Δ_{V} f = Δ_{V} (ιf)ω/(ω + 2π) so Δ_{V} (ιf) = 0. From here it is clear that ι is the desired isomorphism.

□

Proposition 3.9 Let G′ = G ∪ {e} be the graph formed by adding an edge, e, to G. Then Z_{ω}(G) naturally injects into Z_{ω}(G′), and the quotient is of dimension 1 or zero.

Proof If f ∈ Z_{ω}(G), we simply extend it by zero on e to get a member of Z_{ω}(G′). Member of Z_{ω}(G′) restricts to A sin(ωx) along e for some A, and hence any two of them are scalar multiples of each other modulo Z_{ω}(G).

□

First let us observe a corollary of the above two propositions.

Corollary 3.10 Let b the number of ±1’s that appear among Ã’s eigenvalues, i.e.

b = b(G) = \{ \begin{matrix}0 & if ∂G ≠ ∅, \\ 1 & if ∂G = ∅ and G is not bipartite, and \\ 2 & if ∂G = ∅ and G is bipartite. \end{matrix}

Then

dim(Y_{π}) + dim(Y_{2π}) + 2(|V^{o}| − b) = 2|E|.

Hence, if G is bipartite, we further have

dim(Y_{π}) = dim(Y_{2π}) = |E| − |V^{o}| + b.

Proof The first part follows from the above and Weyl’s law. The second part follows from proposition 3.8.

□

To prove theorem 3.5, first note that since we are working with the Dirichlet condition we can assume the boundary is separated— if not, we just give each boundary edge its own boundary vertex.

The corollary above shows that the theorem is true for a tree. Any connected graph is the union of a tree and a number of edges. Hence it suffices to show that if the theorem is true for G then it is true for G with an edge thrown in, G′ = G ∪ {e}.

So assume the theorem is true for G. If b(G) = b(G′) then dim(Y_{π}) + dim(Y_{2π}) increases by 2. But each dimension can increase by at most 1, so they increase precisely by that much, and the theorem holds for G′.

The only change in b that can happen by adding an edge is that b(G) = 2 but b(G′) = 1, i.e. G is bipartite but G′ isn’t. In this case dim(Y_{π}) + dim(Y_{2π}) remains the same. While Z_{π} cannot decrease in going from G to G′, Y_{π}/Z_{π} goes from one to zero dimensional from G to G′. Since Y_{2π}/Z_{2π} remains one dimensional, we have that Z_{2π} increases by one. Once again we see how the Z_{ω}’s and Y_{ω}/Z_{ω}’s change for G′, and it is easy to see the theorem holds there.

□

4 The Wave Equation

We remark that in this section we usually only assume that the graphs are locally finite. This is because the wave equation has finite propogation speed, and “cannot tell” whether or not a graph is finite (in any fixed interval of time).

Definition 4.1 Given a graph, fix non-negative α, β ∈ C^{0}(G), non-negative γ ∈ C^{1}(G), and an interval I ⊂ ℝ. A function u = u(x, t): G × I → ℝ is said to satisfy the wave equation with coefficients α, β, γ if (1) u is continuous on G × I and u( · , t) ∈ C^{2}(G) for all t ∈ I, (2) for all x ∈ G^{o} and t ∈ I^{o} we have u_{tt} exists at (x, t) and is continuous in x, and (3) for fixed t we have

(α dV + β dE)u_{tt} = ∇ · (γ∇u)

as integrating factors. If u vanishes on ∂G × I we say that u satisfies the Dirichlet condition; similarly for the Neumann condition if ∇u vanishes along all edges at all boundary vertices.

We remark that the above equality as integrating factors means that

αu_{tt} = −γΔ_{V} u

at all (x, t) with x ∈ V^{o} and t ∈ I^{o}, and that

βu_{tt} = −γΔ_{E}u + ∇γ · ∇u

at all (x, t) with x ∈ G^{o} \ V and t ∈ I^{o}.

In the above definition we may also allow mixed boundary conditions as in equations 3.4 and 3.5.

The the vertex-based wave equation, we mean the wave equation with coefficients α = γ = 1 and β = 0. In this case Δ_{E}u = 0 and so u must be edgewise linear. As remarked in section 2, Δ_{V} on a finite graph can be viewed as a bounded operator on L_{Dir}^{2}(G, V). As such, for any edgewise linear f ∈ L_{Dir}^{2}(G, V) we can form

u(x, t) = cos(t\sqrt{Δ_{V}} )f = f − t^{2}Δ_{V} f/2 + t^{4}Δ_{V}^{2} f/4! − ⋯

and we easily see it satisfies the wave equation with u(x, 0) = f(x). The boundedness of Δ_{V} implies that if f = χ_{v} is the edgewise linear characteristic function^{4} at v, then for fixed x,

u(x, t) = cos(t\sqrt{Δ_{V}} )χ_{v} = (−1)^{d}t^{2d}N_{x,v}/(2d)! + O(t^{2d+2})

where d is x’s distance to v and N_{x,v} is the number of paths from x to v of length d. It follows that u(x, t) > 0 for small t, and so the vertex-based wave equation does not have a finite wave propagation speed.

Since traditional graph theory is based on Δ_{V} restricted to edgewise linear functions, the above explains why approaching the wave equation with traditional graph theory leads to unsatisfactory results.

A much better model of the wave equation appearing in analysis is the edge-based wave equation, where β = γ = 1 and α = 0. We will show in the next subsection that these waves propagate “along the edges” and have finite wave speed equal to 1.

4i.e., this function is 1 on v, 0 on other vertices, and edgewise linear.

4.1 The Energy Inequality

Many basic properties of the wave equation follow from well-known energy inequality, which we state and apply in this subsection.

If A ⊂ G, then the energy of u = u(x, t) over A at time t is defined to be

Energy(A; t) = ∫_{A}(γ(∇u)^{2} dE + u_{t}^{2}(α dV + β dE)).

For real h > 0 let

A^{h} = {x ∈ G|dist(x, A) < h}.

Now fix coefficients α, β, γ for a wave equation and let c be the smallest constant such that γ ≤ c^{2}β throughout G (we assume this c exists).

Theorem 4.2 Let A be an open set with A^{ct_{0}} of finite type for some t_{0} > 0. Then if u is a solution to the Dirichlet or Neumann wave equation we have

Energy(A^{ct_{0}}; 0) ≥ Energy(A; t_{0}).

The same holds of the mixed boundary condition, as in equations 3.4 and 3.5, provided we add

∫_{K_{2}∩A} γσu^{2} dV

to the energy.

This theorem will be proven in the next subsection; its proof is virtually identical to its well-known proof in analysis.

We remark that the wave equation has a time symmetry, in that if u satisfies the wave equation then so does w(x, t) = u(x, −t). We may therefore conclude the symmetric fact that

Energy(A; 0) ≤ Energy(A^{ct_{0}}; t_{0}).

From the energy inequality we easily conclude the following proposition:

Proposition 4.3 Assume G is locally finite, that β is strictly positive on G, and that c exists as before (i.e. γ ≤ c^{2}β everywhere). Let u be a solution to the wave equation on G × [0, T] with u(x, 0) = 0 and u_{t}(x, 0) = 0 for all x within a distance ct to a fixed y ∈ G. Then u(y, t) = 0.

Proof For any ϵ > 0 we have

Energy({y}^{c(t−ϵ)}; 0) = 0.

We conclude that u_{t}(y, s) vanishes from s = 0 to s = t − 2ϵ, and hence u(y, t − 2ϵ) = 0. Now we let ϵ → 0 and use the continuity of u.

□

Some immediate corollaries of this are:

Corollary 4.4 If u, w are two solutions to the wave equation such that u and w agree at time t = 0 on all points within distance ct to y, and the same for u_{t} and w_{t}, then u(y, t) = w(y, t). In other words, the value of u(y, t) depends only on the value of u at a fixed time in the “space-time cone of speed c at y.” In other words, this wave equation has finite speed of wave propagation which is bounded by c.

Corollary 4.5 Fixing u( · , 0) and u_{t}( · , 0), there is at most one solution, u(x, t) for t > 0, to the wave equation.

4.2 A Proof of the Energy Inequality

Let I ⊂ ℝ be an interval. By a (graph-time) vector field on G × I we mean a pair (G, F) where F = F (t) is an integrating factor on G and G = G(t) is vector field on G both depending on t ∈ I. By its divergence we mean

∇_{gt} · (G, F) = ∇ · G + F_{t},

which is an integrating factor that depends on time, t, where by F_{t} we mean the partial derivative of F with respect to t, i.e. we differentiate F ’s dV component and its dE component with respect to time.

Proposition 4.6 Consider a divergence free graph-time vector field, (G, F), i.e. ∇ · G + F_{t} = 0 as a boundary inclusive equality. Write F = F_{V} dV + F_{E} dE and assume that F_{V} ≥ 0 at all vertices, and

cF_{E} ≥ |G|

on (G \ V) × I. Then if A is any open set with A^{ct_{0}} of finite type, and if 0, t_{0} ∈ I, then

I(t) = ∫_{A^{c(t_{0}−t)}} F (t)

is a non-increasing function in t ∈ [0, t_{0}].

The energy inequality in the proceeding section follows almost at once by taking

F = γE(∇u)^{2} + (αV + βE)u_{t}^{2} and G = −2γu_{t}∇u,

adding γσu^{2}V|_{K_{2}} to F for the mixed boundary condition. Proof Let S(t) = A^{c(t_{0}−t)}. If ∂S(t) contains a vertex, then I(t) is right continuous at t, and has a jump (if any) from the left of

I(t − 0) − I(t) = ∑_{x∈V^{o}∩∂S(t)} F_{V} (x)V(x).

Next partition ∂S(t) into interior and boundary points,

B^{o} = ∂S(t) ∩ G^{o} and B^{∂} = ∂S(t) ∩ ∂G.

B^{o} will contain no vertices for all but finitely many t. If B^{o} contains no vertex, then using proposition 2.21 we see that

I′(t) = − ∑_{x∈B^{o},e∋x} F_{E}(x, t)ca_{e} + ∫_{S(t)∪B^{∂}} F_{t}(t)

(where F_{t} contains both a dV term and a dE term). By taking S(t) and adding to it ∂S(t) as new vertices each of weight 1, we get a graph, G_{t}; taking F_{V} = 0 at all new vertices, we may write:

∫_{S(t)∪B^{∂}} F_{t}(t) = ∫_{G_{t}\B^{o}} F_{t}(t) = − ∫_{G_{t}\B^{o}} ∇ · G(t)

= ∫_{B^{o}} ñ · G(t) = ∑_{x∈B^{o},e∋x} n_{e,x} · G(x, t)a_{e},

using the divergence theorem.

Recalling that n_{e,x} is a unit vector, we have

−F_{E}(x, t)c + n_{e,x} · G(x, t) ≤ −F_{E}(x, t)c + |G(x, t)| ≤ 0

for all x, t. Hence

I′(t) = ∑_{x∈B^{o},e∋x} a_{e}(−F_{E}(x, t)c + n_{e,x} · G(x, t)) ≤ 0.

We have shown that I(t) is non-increasing at all but finitely many points (i.e. the t’s with B^{o} containing a vertex), and at these finitely many points we know that I(t) is continuous or has a decreasing jump. Hence I(t) is non-increasing.

□

The proposition is usually proven (in analysis) by invoking a space-time divergence theorem on a truncated cone in space-time (or graph-time here), such as those (x, t) with dist(x, A) < c(t_{0} − t) (see, for example, [Smo83] chapter 4 or [CH89]). While this approach also works, setting up a graph-time divergence theorem seems like more trouble than its worth for our purposes at this point.

4.3 More General Wave Equations

We remark that one can generalize the uniqueness results for the wave equation, i.e. corollaries 4.4 and 4.5, to the same results for a wave equation of the form

(α dV + β dE)u_{tt} = ∇ · (γ∇u) + δ · ∇u + ϵu,

where δ is a C^{0} vector field and ϵ is a C^{0} function, and we assume β never vanishes. The proof is a simple adaptation of the analysis proof given in, for example, Smoller’s book ([Smo83]). We define the energy exactly the same as before (ignoring δ and ϵ), but now prove

e^{Kt_{0}}Energy(A^{ct_{0}}; 0) ≥ Energy(A; t_{0})  (4.1)

for some constant K depending on δ, ϵ, provided that u and u_{t} vanish on A^{ct_{0}} at t = 0. Uniqueness with “propagation speed” at most c follows as before.

We shall outline the proof of equation 4.1 when δ = 0; the general case is a bit messier but similar (see [Smo83] for details). First we notice that if all is the same as in proposition 4.6 except that ∇ · G + F_{t} does not necessarily vanish (where by F and G we mean F = γE(∇u)^{2} + (αV + βE)u_{t}^{2} and G = −2γu_{t}∇u), then we have

I(t) ≤ I(0) + ∫_{0}^{t} ∫_{A^{c(t_{0}−s)}}(∇ · G + F_{t}) ds.

Hence setting

E(t) = Energy(A^{c(t_{0}−t)}; t)

for 0 ≤ t ≤ t_{0}, we have for such t,

E(t) ≤ E(0) − 2 ∫_{0}^{t} ∫_{A^{c(t_{0}−s)}} ϵu(x, s)u_{t}(x, s) dE(x) ds  (4.2)

The integral in the right-hand-side can be bounded by

|∫_{0}^{t} ∫_{A^{c(t_{0}−s)}} uu_{t}| ≤ ∫ ∫ u^{2}/2 + ∫ ∫ u_{t}^{2}/2.

The u_{t}^{2}/2 term integrated over space is bounded by a constant times E(t) (since β vanishes nowhere), and the u^{2}/2 can be bounded by a constant times t^{2} times a u_{t}^{2} integral by Poincaré’s inequality (see [Smo83]). It easily follows that the double integral in equation 4.2 is bounded by a constant times ∫_{0}^{t} E(s) ds, and hence

E(t) ≤ E(0) + K ∫_{0}^{t} E(s) ds

for a constant K. Gronwall’s inequality implies E(t) ≤ e^{Kt}E(0), which is just equation 4.1.

4.4 Differentiability and the Wave Equation

In this subsection we show how to prove the existence of a solution to the wave equation for sufficiently “differentiable” initial conditions. On the circle, i.e. ℝ/(2πℤ), there is a rough correspondence between differentiability and having Fourier coefficients decaying. We shall use the same for graphs, to give a nice description of when we are sure that the wave equation has a solution.

Let f_{1}, f_{2}, … be the eigenfunctions of Δ_{E} with eigenvalues λ_{1}, λ_{2}, … with some boundary conditions of any type specified before. Let D^{k} (which depends on the boundary conditions) be those formal sums ∑_{i} a_{i}f_{i} with ∑_{i} i^{k}|a_{i}| < ∞ (here k is any real, although typically a non-negative integer). Let B^{k} be the same, except that the a_{i}’s are subject to the weaker condition that i^{k}|a_{i}| is bounded in i. Let Diff^{k} be those functions f ∈ C^{k} such that for j = 0, …, k − 1 we have (1) f^{(j)}(v, e) depends only on v if j is even, where f^{(j)}(v, e) is the j-th derivative of f at v along e, and (2) the sum of f^{(j)}(v, e) over all e for fixed v is zero for all v, if j is odd.

It is not hard to prove the following facts:

Proposition 4.7 We have natural inclusions B^{k+1+ϵ} ⊂ D^{k} ⊂ B^{k} for any k and ϵ > 0, and inclusions D^{k} ⊂ Diff^{k} ⊂ B^{k} for any non-negative integer k.

We remark that Diff^{k}’s compatibility with D^{k}, B^{k} makes it, in some sense, a better notion of differentiability than C^{k} defined in section 2. Proof The first inclusions are straightforward. The inclusion D^{k} ⊂ Diff^{k} follows by viewing the formal sum as an absolutely convergent sum of functions whose derivatives up to k-th order also form an absolutely convergent sum (here we use the periodic nature of the eigenpairs). Finally the inclusion Diff^{k} ⊂ B^{k} follows by integration by parts of the inner product (f, f_{i}) for an f ∈ Diff^{k} along each edge: ∫_{0}^{1} f(x)A_{e} cos(ωx + B_{e}) is proportional to the integral of ω^{−k}f^{(k)}(x) times sine or cosine of plus or minus ωx + B_{e} plus boundary terms. The boundary terms at v ∈ V^{o} are proportional to sums over e of f^{(j)}(v, e)A_{e} times sine or cosine ωx + B_{e}. Knowing that A_{e} cos(B_{e}) is independent of e (for a given v, with x = 0 corresponding to v), and knowing that the sum of A_{e} sin(B_{e}) vanishes (since Δ_{V} f_{i} = 0 for all i), we see that the boundary terms at V^{o} disappear; similarly we see that boundary terms at boundary vertices vanish. Now we use Weyl’s law and the fact that f ∈ C^{k} to see that i^{k}(f, f_{i}) is bounded.

□

We now state an existence theorem in terms of D^{2}; it follow from the above proposition that our theorem also applies to the class Diff^{4}, which is easier to understand, in a sense, than D^{2}.

Proposition 4.8 Let g, h ∈ D^{2}. If g = ∑ a_{i}f_{i} and h = ∑ b_{i}f_{i}, then

u(x, t) = ∑_{i} f_{i}[a_{i} cos(\sqrt{λ_{i}} t) + \frac{b_{i}}{\sqrt{λ_{i}}} sin(\sqrt{λ_{i}} t)]  (4.3)

is a solution to the wave equation with u( · , 0) = g and u_{t}( · , 0) = h.

Proof We need to know that u_{tt} exists, and if g, h ∈ D^{2} then the sum of twice differentiated terms is absolutely convergent and this u_{tt} exists. The rest is an easy verification.

□

We remark that for any g, h in, say, L^{2}, g and h will have eigenfunction expansions. It makes sense to define u(x, t) by the formal sum above (in equation 4.3), which for fixed t will always lie in L^{2} (although u_{tt} need not exist).

4.5 Chebyshev Polynomials and the Wave Operator

We assume again that G is finite in this subsection. Let f_{i}, λ_{i} be as in the preceeding subsection, and set Summ to be D^{0} in the notation of the previous section, i.e.

Summ = {∑_{i} a_{i}f_{i} | ∑ |a_{i}| < ∞}.

Elements of Summ may be viewed as formal sums, or we may identify them with the bounded function on G to which they converge (since the f_{i} are uniformly bounded). Summ is the set of functions with a summable eigenfunction coefficient series; it is easy to see that it contains, for example, H^{1}(G). The map sending f_{i} to its restriction on vertices extends to a continuous map from Summ to L^{∞}(G, V). Since G is finite this gives rise to a continuous map M_{E→V} : Summ → L^{2}(G, V).

If g ∈ Summ with g = ∑ a_{i}f_{i}, then

(cos \sqrt{Δ_{E}})g = ∑ a_{i}(cos \sqrt{λ_{i}})f_{i}

lies in Summ, and we know

M_{E→V} (cos \sqrt{Δ_{E}})g = ∑ a_{i}(cos \sqrt{λ_{i}})M_{E→V} f_{i}.

Since 1 − cos \sqrt{λ_{i}} is the Δ_{V} eigenvalue corresponding to M_{E→V} f_{i} and Ã = I − Δ_{V}, we have

ÃM_{E→V} = M_{E→V} cos \sqrt{Δ_{E}}

as maps from Summ to L^{2}(G, V), assuming all edge lengths are 1. It follows that for any polynomial, P, we have

P (Ã)M_{E→V} = M_{E→V} P (cos \sqrt{Δ_{E}}).

If T_{k} is the k-th Chebyshev polynomial, given by

T_{k}(cos x) = cos(kx),

we have

T_{k}(Ã)M_{E→V} = M_{E→V} cos(k\sqrt{Δ_{E}}).

We conclude the following theorem.

Theorem 4.9 Let all edge lengths be 1. Let g ∈ Summ, and let u be the formal solution to the wave equation as in equation 4.3 with h = 0. Then for any integer k and interior vertex v we have

u(v, k) = T_{k}(Ã)M_{E→V} g.

So if we wish to know this wave equation solution at vertices and at only integral times, we need only know the initial condition at the vertices. The values of the solution there are given in term of Chebyshev polynomials of the normalized adjacency matrix. Notice that knowing the values of u at non-integral times requires knowning f along the edges.

Notice that theorem 4.9 is valid for infinite (locally finite) graphs, since the wave equation solution is determined locally for any finite time, and the equality in theorem 4.9 is a local statement as well.

We finish this subsection by remarking that if we ignore the map M_{E→V}, we can say that Ã “acts like” cos \sqrt{Δ_{E}}. Noting that Ã is I − Δ_{V} for an appropriate graph theoretic Laplacian, Δ_{V}, we can see that I − Δ_{V} “acts like” cos \sqrt{Δ_{E}}.

4.6 Wave Propagation through Vertices

Using theorem 4.9 it is not hard to see what happens when a wave is sent through a vertex. More precisely, let G be the infinite d-regular star^{5}, i.e. G’s vertices are v_{0} union v_{i,j} with i = 1, …, d and j a positive integer, and G’s edges are {v_{0}, v_{i,1}} for all i, and {v_{i,j}, v_{i,j+1}} for all i and for all positive j (see figure below).

Taking g to be a function which is zero on all vertices except v_{1,j} for some j ≥ 2, we apply theorem 4.9 to see that of the “wave” traveling towards v_{0}, we have (2/d) − 2 of the wave comes back along the i = 1 edge, and 2/d of it travels down each i > 1 edge.

This motivates the following theorem. We state this theorem in terms of the length 1 d-regular star, by which we mean the graph, G, as above, except we restrict j to take on only the value 1. We endow the edges of G with standard coordinates x_{1}, …, x_{d} where x_{i}(0) = v_{0} and x_{i}(1) = v_{i,1}.

5Note that the wave equation effectively ignores vertices of degree 2, i.e. one gets the same equation if one treats the two edges incident with the vertex as one longer edge. So the infinite d-regular star is equivalent to a graph with one degree d vertex and d edges of infinite length.

Theorem 4.10 Let u(x, t) be the solution to the wave equation for 0 ≤ t ≤ 1/4 given by

u(x_{i}, t) = \{ \begin{matrix}f(x_{1} + t) & for i = 1, \\ 0 & otherwise, \end{matrix}

where f is any twice differentiable function supported on (1/4, 3/4). Then the solution for 0 ≤ t ≤ 5/4 to the wave equation exists and is given by

ũ(x_{i}, t) = \{ \begin{matrix}f(x_{1} + t) + [(2/d) − 1]f(t − x_{1}) & for i = 1, \\ (2/d)f(t − x_{i}) & otherwise. \end{matrix}

Notice that this theorem tells us how waves propagate through vertices. Also, notice that we know that ũ is unique. Proof Clearly ũ satisfies the wave equation on edge interiors. At v_{0}, the only vertex of interest for t ≤ 5/4, we have ũ is continuous (taking the limiting value 2f(t)/d along each edge at v_{0}) and satisfies Δ_{V} ũ = 0 there. Hence ũ satisfies the wave equation.

□

4.7 Finite Propagation Speed of Wave Operators

There are a number of operators on L^{2}(G, E) that arise from the wave operator, which have a “finite speed of propagation.” We mention one classical one, and a generalization of it. First we need some definitions.

By the support of a function, f, in L^{2}(G, E) we mean the complement of the union of those open sets, U for which f = 0 almost everywhere in U.

Definition 4.11 Let A_{t} be a family of bounded (everywhere defined) operators on L^{2}(G, E) indexed on t ≥ 0. We say that A_{t} have speed of propagation at most c if (A_{t}f, g) = 0 for any f, g ∈ L^{2}(G, E) and t with the supports of f and g a distance at least ct.

Definition 4.12 A subset, D, of L^{2}(G, E) is called supportingly dense if for any f ∈ L^{2}(G, E) and ϵ > 0 there is an f̃ ∈ D such that ∥f − f̃∥_{2} < ϵ and (each point of) the support of f̃ is within a distance ϵ of the support of f.

We remark that in our propagation speed definition, rather than requiring f, g ∈ L^{2}(G, E), it suffices to take f, g ∈ D where D is any supportingly dense subset of L^{2}(G, E). We also remark that standard mollification arguments show that for any k, Diff^{k} is supportingly dense; it follows that B^{k} and D^{k} are, as well.

Consider the operator:

W_{t} = cos(t\sqrt{Δ}).

By the spectral theorem this can be viewed as an operator on L^{2}(G, E) whose norm is bounded by 1. We know by proposition 4.8 that W_{t} restricted to D^{2} ∩ L^{2}(G, E) has propagation speed at most 1. Since D^{2} is supportingly dense in L^{2}(G, E) we see that W_{t} has speed of propagation ≤ 1.

Next for any a ∈ ℝ consider the operator:

W_{t,a} = h(t^{2}(Δ − a)),

where

h(x) = 1 − \frac{x}{2!} + \frac{x^{2}}{4!} − \frac{x^{3}}{6!} + ⋯ = \{ \begin{matrix}cos \sqrt{x} & if x ≥ 0, \\ cosh \sqrt{−x} & if x < 0. \end{matrix}

So W_{t,0} is just W_{t} as above. Since Δ is positive semidefinite we have ∥W_{t,a}∥ ≤ cosh(t\sqrt{a}). The analogue of proposition 4.8 for the wave equation u_{tt} = −Δu + au is easily verified, and we conclude (using subsection 4.3) as we did for W_{t} that

Proposition 4.13 For fixed a, the propagation speed of W_{t,a} is ≤ 1.

5 Applications

In this section we give examples of how to apply our edge-based approach to get graph theoretic results from analysis results. We give a new bound on eigenvalues based on set distances in graph theory; the bound it gives on diameters can be better or worse than the well known bound of Chung, Faber, and Manteuffel (in [CFM94]); our technique is very simple and works in analysis (to give the result of Friedman and Tillich in [FT]). We also show, for example, that the graph diameter inequalities of Chung, Grigor’yan, and Yau in [CGY96, CGY97], which mildly generalize that of Chung, Faber, and Manteuffel (in [CFM94]), is optimal to first order, in a certain sense, for small Laplacian eigenvalue. We give other results that illustrate our ability to translate from analysis to graph theory, although these other results do not improve the best known graph theory results.

5.1 Distances and Diameter: Using Old Results

A number of papers have inequalities relating distances to sets or diameters of a space to Laplacian eigenvalues, both for manifolds and graphs (see [AM85, Moh91, LPS88, CFM94, CGY96, BL97, CGY97]). In [FT] the philosophy that I − Δ_{G} “acts like” cos \sqrt{Δ_{E}} of the preceeding section is used to apply graph theoretic techniques (namely those of [CGY97]) to analysis and get an improved eigenvalue bound based. Here we go the other way, taking analysis results or more general results, and apply them to get graph theoretic results. The result we obtained is not the best known, but it is better than some results, especially one that can be derived from the same technique using the vertex-based Laplacian. However, in the next subsection we give a distances/eigenvalues technique the yields new results in graph theory.

Consider the result of Bobkov and Ledoux, which states that for any metric probability space, (M, ρ, μ), and disjoint Borel sets X, Y we have

\sqrt{λ} ρ(X, Y) ≤ − log(μX μY)  (5.1)

where ρ(X, Y) is the distance from X to Y and λ is the optimal constant in the Poincaré inequality (in other words, λ is the first non-zero Neumann eigenvalue in the case of a compact manifold or finite graph). Let us apply this to bounding the diameter of a graph.

One way is to directly apply equation 5.1 to the vertex-based situations, with λ = λ_{V}, the vertex-based Laplacian eigenvalue. We get μX = |X|/n, and we take X, Y to consist of single points of distance D where D is the diameter. We conclude:

\sqrt{λ_{V}} D ≤ log(n^{2}) = 2 log n

or

D ≤ 2 log n/\sqrt{λ_{V}} .

Here λ_{V} is the first non-zero eigenvalue of the Laplacian I−Ã where Ã is the normalized adjacency matrix. Notice that if our graph is d-regular, then λ_{V} = λ_{T} /d where λ_{T} is the first non-zero eigenvalue of the traditional graph theoretic Laplacian. We conclude:

D ≤ 2 log n\sqrt{d/λ_{T}} .

Alternatively we may apply equation 5.1 to the edge-based Laplacian. Notice that the similar and slightly weaker inequalities of [CGY96, CGY97] require the Laplacian, Δ, to have cos(t\sqrt{−Δ}) extend supports of functions by a distance at most t. So our edge-based Laplacian could be used with these earlier results, whereas the vertex-based Laplacian could not. We take X, Y to be balls of size 1/2 about two points of distance D, the diameter. We conclude:

\sqrt{λ_{E}} (D − 1) ≤ log(n^{2}) = 2 log n.

Seeing as \sqrt{λ_{E}} = cos^{−1}(1 − λ_{V}), we have

D − 1 ≤ \frac{2 log n}{cos^{−1}(1 − λ_{V})}.

But it is easy to see that cos^{−1}(1 − a) ≥ \sqrt{2a} for any a. Hence we have

D − 1 ≤ \sqrt{2/λ_{V}} log n.

In the d-regular case this gives

D − 1 ≤ \sqrt{(2d)/λ_{T}} log n.  (5.2)

We conclude: (1) with the same technology, i.e. using equation 5.1, the edge-based technique does better than the vertex-based technique by roughly a factor of \sqrt{2}, and (2) in previous Laplacian bounds (e.g. [CGY96, CGY97]) the edge-based technique can be applied whereas the vertex-based technique cannot (by support extending restrictions that are equivalent to the wave equation having propagation speed 1).

It is interesting to note that the edge-based diameter bound we derived (in equation 5.2) improves the orginal Alon-Milman bound^{6} of

D ≤ 2⌊\sqrt{(2d/λ_{T})} log_{2} n⌋

(see [AM85]), in the case where d/λ_{T} and n are large. Similarly we have improved Mohar’s improvement (see [Moh91]) of the Alon-Milman result, taking λ_{∞} ≤ 2d (the highest Laplacian eigenvalue^{7}). But the result of Chung, Faber, and Manteuffel (see [CFM94]) improves on our edge-based result by a factor of 2. In fact, it is precisely this factor of 2 that we gain in applying the result in Chung, Faber, and Manteuffel to analysis, in [FT], using the relation in this paper between graph Laplacians and analysis-like (e.g. edge-based) Laplacians.

5.2 Distances and Diameters: New Results

In this subsection we give a new way of proving distance/eigenvalues or diameter/eigenvalue results. Graph theoretically this yields a new result, which is an edgebased analogue of the Chung, Faber, and Manteuffel (see [CFM94]) result; our new results cannot be compared to that of Chung, Faber, and Manteuffel— it can yield better or worse results. This proof also carries over to analysis, where it gives a different (and in some sense shorter) proof of the Friedman-Tillich result in [FT]. But however different our proofs or results are, they can be viewed as variants of older results stemming from the same basic technique used in [CGY97] and [FT].

Let X_{0} denote the constants in L^{2}(G, E), and X_{1} the orthogonal complement of X_{0}; for i = 0, 1 let π_{i} denote the projection onto X_{i} (so π_{0} + π_{1} is the identity). Let W_{t,a} be the operators defined at the end of section 4, and fix a = λ_{E} to be the first non-zero eigenvalue of Δ.

6It is interesting that this bound is often misquoted, as the authors use [a] to denote ⌊a⌋ (the greatest integer ≤ a) without ever explicitly saying so in the paper. Many authors incorrectly guess the meaning of [a].

7Since we are thinking of d/λ_{T} as being large, it seems reasonable to expect that that λ_{∞} should not be far from 2d.

Proposition 5.1 If f, g are two functions whose supports are at a distance of at least d, we have

cosh(d\sqrt{λ_{E}}) ≥ \frac{∥π_{1}f∥∥π_{1}g∥}{∥π_{0}f∥∥π_{0}g∥}.

Proof By proposition 4.13 we have

0 = (W_{d,a}f, g) = (W_{d,a}π_{0}f, π_{0}g) + (W_{d,a}π_{1}f, π_{1}g).

Now

(W_{d,a}π_{0}f, π_{0}g) = ± cosh(d\sqrt{λ_{E}})∥π_{0}f∥∥π_{0}g∥

since π_{0}f, π_{0}g are both constants. Since W_{d,a} restricted to X_{1} has norm at most one, we have

|(W_{d,a}π_{1}f, π_{1}g)| ≤ ∥π_{1}f∥∥π_{1}g∥,

and the proposition follows.

□

Corollary 5.2 Let X, Y be disjoint measurable subsets of distance ≥ d. Then

d\sqrt{λ_{E}} ≤ cosh^{−1}(\sqrt{\frac{E(X^{c})E(Y^{c})}{E(X)E(Y)}}).

Proof Take f, g to be the respective characteristic functions of X, Y.

□

We finish this subsection with a discussion of the above proposition and its corollary. First of all, these proofs carry right over to analysis, where they yield the results of

Friedman and Tillich (in [FT]) with a considerably simpler proof; however, the basic idea that (W_{d,a}f, g) = 0 based on the supports of f, g the the speed of propagation of W appears before.

Second, the above proposition and corollary can be generalized to k functions or k sets for any k ≥ 2, with the same technique that appears in [CGY96], also used in [CGY97, FT]. In the analysis case we recover the results for k functions or sets that appear in [FT]. For graphs, our corollary would read that if X_{1}, …, X_{k} were disjoint measurable subsets any two of which had supports of distance ≥ d, then

d\sqrt{λ_{E}} ≤ min_{i≠j} cosh^{−1}(\sqrt{\frac{E(X_{i}^{c})E(X_{j}^{c})}{E(X_{i})E(X_{j})}}).

Our proposition would read similarly.

Finally, we remark that the above corollary yields a diameter result that can be better (or worse) than that of Chung, Faber, and Manteuffel (see [CFM94]). Similarly our corollary can be better or worse than the comparable theorem in [CGY97]. For example, the Chung, Faber, and Manteuffel result states that in a regular graph

(D − 1) cosh^{−1}(1 + \frac{2λ_{V}}{λ_{n} − λ_{V}} ) ≤ cosh^{−1}(n − 1),

where D is the diameter, n = |V |, and λ_{V} , λ_{n} are respectively the smallest and largest positive Δ_{V} eigenvalues. Taking balls of radius δ/2 about two points of distance D and applying corollary 5.2 we get

(D − δ)\sqrt{λ_{E}} ≤ cosh^{−1}(2n/δ − 1)

for any δ ≤ 2. It follows that the result obtained here, taking δ = 2, is better than the result in [CGY97], provided that λ_{V} and 2 − λ_{n} are both ≤ c/ log n for a constant, c (using cos \sqrt{λ_{E}} = 1 − λ_{V}).

5.3 Invariants

A typical spectral invariant studied in the analysis literature is the wave invariant

W (t) = Trace(cos t\sqrt{Δ_{E}}) = ∑_{j}(cos t\sqrt{λ_{j}}),

with λ_{j} running through all Laplacian eigenvalues. This sum can be understood in several ways; here we think of

W̃(t) = ∑_{j}(e^{it\sqrt{λ_{j}}})

as a complex analytic function defined on the subset of complex numbers with positive imaginary part, and then we extend W̃ analytically to the whole complex plane; W is just the real part of W̃.

It is well known that in analysis the real singularities of W are at t = 0 and t being (plus or minus) the length of a closed geodesic. If all edges of a graph have length one, then we know we have α_{1}, …, α_{2|E|} such that the edge-based eigenvalues (with their respective multiplicities) are precisely those squares of α_{j} + 2πℤ_{≥0}. We have

W̃(t) = \frac{1}{1 − e^{2πit}} ∑_{j=1}^{2|E|} e^{itα_{j}}.

This has a pole at tℝ precisely when t = 0 or t is an integer with ∑ e^{itα_{j}} ≠ 0.

To understand the vanishing or not of ∑ e^{itα_{j}}, consider that the α_{j}’s are of two types; one type is a (π, 2π) pair coming from an edge and interior vertex count, and such α_{j}’s cancel in the sum ∑ cos(itα_{j}) for t an odd integer and contribute 2 when t is even; the other type is a α, 2π − α pair with

e^{itα} + e^{it(2π−α)} = 2 cos(tα)

for t an integer. Hence this sum is essentially the trace of the t-th Chebyshev polynomial in Ã.

It follows that the first odd t > 0 for which W̃ has a pole is the length of the smallest odd cycle. However it doesn’t seem like such a simple statement holds for higher odd values of t or even values, and so the invariant W̃ is not entirely analogous to its analysis counterpart.

It is natural to ask if any spectral, edge-based invariants (such as those whose analysis analogues are interesting, for example) yield new and interesting graph invariants. Such invariants would, in particular, include traces of Chebyshev polynomials of Ã when the edge lengths are one.

5.4 Cheeger’s Inequality

In this section we mention that Cheeger’s inequality holds for the edge-based Laplacian as well as the vertex-based, but the second one, at least for r-regular graphs yields the first one. We will require some notions from [FT99].

Consider an open subset of A ⊂ G whose boundary contains no vertices, and let A(∂A) be the “area” of A’s boundary (see [FT99]); this is just the sum of a_{e} for each boundary point of A lying on e. Also E(A) is just the total E measure of A, and we set

h_{E} = min_{E(A)≤E(G)/2} \frac{A(∂A)}{E(A)}.

The co-area formula of [FT99] and the arguments to prove Cheeger’s inequality immediately carry over here to yield:

λ_{E} ≥ h_{E}^{2}/4.  (5.3)

We can compare this to Cheeger’s inequality for the vertex-based case (i.e. Dodziuk’s inequality, see [Dod84, FT99]),

λ_{V} ≥ h_{V}^{2} /2  (5.4)

for the 1-regular graphs (see section 2), where

h_{V} = min_{B⊂V, V(B)≤ V(V)/2} \frac{E(E(B, B^{c}))}{V(B)},

where E(B, B^{c}) denotes the set of edges with one endpoint in B and once in B^{c}.

Let us compare these two Cheeger’s inequalities, in case the graph is d-regular in the traditional sense (each vertex is the endpoint of d edges) with unit edge lengths and weights. We consider now the graph G derived from it, where V at any vertex is taken to be d so as to make the graph 1-regular.

We shall need a simple lemma

Lemma 5.3 For a 1-regular graph h_{V} ≥ h_{E}/2.

Proof Let B be the subset of vertices of size smaller than V(V)/2 for which

h_{V} = \frac{E(E(B, B^{c}))}{V(B)},

For a subset X of vertices we denote by X_{t} the set of points which lie on the edges which have both endpoints on B or are within a distance t from X. Note that

E(B_{1/2}) + E(B^{c}_{1/2}) = E(G).

It follows that the measure of one of these two sets is smaller than or equal to V(G)/2. Case 1: E(B_{1/2}) ≤ V(G)/2.

Here \frac{A(∂B_{1/2})}{E(B_{1/2})} ≥ h_{E}. Since E(E(B, B^{c})) = A(∂B_{1/2}) and V(B) ≤ 2E(B_{1/2}), we obtain

h_{V} = \frac{E(E(B, B^{c}))}{V(B)} ≥ \frac{A(∂B_{1/2})}{2E(B_{1/2})} ≥ h_{E}/2.

Case 2: V(B^{c}_{1/2}) ≤ E(G)/2. This implies that V(V)/4 = E(G)/2 ≥ V(B^{c}_{1/2}) ≥ V(B^{c})/2, so B^{c} is also of measure smaller than or equal to V(V)/2, and therefore V(B) = V(B^{c}) = V(V)/2. which means that

h_{V} = \frac{E(E(B, B^{c}))}{V(B^{c})},

By using the same arguments as in the previous case (with B^{c} replacing B) we also get h_{V} ≥ h_{E}/2.

□

Now notice that

λ_{E} = (cos^{−1}(1 − λ_{V}))^{2} ≥ 2λ_{V} .

Hence

λ_{E} ≥ 2λ_{V} ≥ h_{V}^{2} ≥ h_{E}^{2}/4.

In other words for 1-regular graphs Cheeger’s inequality for vertices (i.e (5.4)) implies the Cheeger inequality for edges (i.e (5.3)).

5.5 Optimal Distance Bounds

In this section we prove the following theorem.

Theorem 5.4 Let C, C_{1}, C_{2} be constants such that the following holds. For any graph with edge lengths one, whose diameter D is realized by two vertices, u, v, we have

D − 1 ≤ \frac{C}{\sqrt{2λ_{V}} + C_{1}λ_{V}} log (\frac{C_{2}V(V)^{2}}{V(u)V(v)})  (5.5)

Then C ≥ 1/2. The same is true if we insist that the graph is 1-regular.

The bound of Chung, Faber, and Manteuffel (in [CFM94]) implies equation 5.5 with C = 1/2 assuming V is constant; the generalization to general V is implied by the results in [CGY96, CGY97] (with different constants C_{2} in the two articles). Actually, there they assume the edge weights are integral; but this assumption clearly implies the same for rational edge weights, and therefore arbitrary real edge weights. So regarding λ_{V} as small, these inequalities are optimal to first order.

Our proof is based on a standard metric probability space, the “exponential distribution on the non-negative reals,” or on a standard Riemannian manifold, the surface of revolution of y = e^{−x} with x non-negative. We model this in a graph by taking a sequence of edges with edge weight exponentially decreasing. These analysis examples provided the analysis bound analogous to C ≥ 1/2 (see [FT]). Proof Fix a small η ∈ (0, 1), and let r = 1 − η. Fix an integer D > 0. Consider the graph, G, whose vertices are the integers, V = {0, 1, …, D}, with an edge from i to i + 1 of weight r^{i} for all non-negative integers i < D.

Making G into a 1-regular graph is done by taking V(i) = r^{i−1} + r^{i} for i ≠ 0, D, dropping one of these summands when i = 0 or i = D. Here the vertices which are the furthest from each other are 0 and D, and therefore

log (\frac{V(V)^{2}}{V(u)V(v)}) = log (\frac{4 (\frac{1−r^{D+1}}{1−r} )^{2}}{1 · r^{D}} ) ≤ K(r) − D log r.

We obtain a lower bound on λ_{V} by using Cheeger’s inequality 5.4. Obviously to find Cheeger’s constant h_{V} we just need to consider vertex sets which are connected, i.e of the form B = {a, a + 1, …, b}.

We have to distinguish between two cases : a > 0 or a = 0. In the first case

\frac{E(E(B, B^{c}))}{V(B)} = \frac{r^{a−1} + 1_{\{b≠D\}}r^{b}}{r^{a−1} + 2 ∑_{i=a}^{b−1} r^{i} + 1_{\{b≠D\}}r^{b}} ≥ \frac{1}{2(1 + r + r^{2} + ⋯)} = \frac{1 − r}{2}.

In the second case we get the same lower bound with a slightly more tedious calculation. First we note that in this case b ≠ D (since V(B) ≤ V(V)/2) and therefore

V(B) = r^{b} + 2 ∑_{i=0}^{b−1} r^{i} ≤ V(V)/2 = \frac{1 − r^{D+1}}{1 − r}  (5.6)

This implies that

r^{b} ≥ \frac{1 + r^{D+1}}{1 + r}  (5.7)

We use the previous upper bound on V(B), and this lower bound on r^{b} to obtain

\frac{E(E(B, B^{c}))}{V(B)} = \frac{r^{b}}{V(B)} ≥ \frac{(1 + r^{D+1})(1 − r)}{(1 + r)(1 − r^{D+1})} ≥ \frac{1 − r}{2}

By using (5.4) it follows that

λ_{V} ≥ (1 − r)^{2}/8 = η^{2}/8,

and therefore

D − 1 ≤ \frac{C}{η/2 + C_{1}η^{2}/8} (K(r) − D log r) .

Taking D → ∞ we conclude

1 ≤ −\frac{C}{η/2 + C_{1}η^{2}/8} log(1 − η).

Taking η → 0^{+} yields 1 ≤ 2C.

□

References

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

[BL97] S. Bobkov and M. Ledoux. Poincaré’s inequalities and Talagrand’s concentration phenomenon for the exponential distribution. Probab. Theory Related Fields, 107(3):383–400, 1997.

[CFM94] F. R. K. Chung, V. Faber, and Thomas A. Manteuffel. An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian. SIAM J. Discrete Math., 7(3):443–457, 1994.

[CGY96] F. R. K. Chung, A. Grigor’yan, and S.-T. Yau. Upper bounds for eigenvalues of the discrete and continuous Laplace operators. Adv. Math., 117(2):165– 178, 1996.

[CGY97] F. R. K. Chung, A. Grigor’yan, and S.-T. Yau. Eigenvalues and diameters for manifolds and graphs. In Tsing Hua lectures on geometry & analysis (Hsinchu, 1990–1991), pages 79–105. Internat. Press, Cambridge, MA, 1997.

[CH89] R. Courant and D. Hilbert. Methods of mathematical physics. Vol. II. John Wiley & Sons Inc., New York, 1989. Partial differential equations, Reprint of the 1962 original, A Wiley-Interscience Publication.

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

[Fri69] Avner Friedman. Partial Differential Equations. Holt, Rinehart and Winston, 1969.

[Fri93] J. Friedman. Some geometric aspects of graphs and their eigenfunctions. Duke Mathematical Journal, 69(3):487–525, March 1993.

[FT] Joel Friedman and Jean-Pierre Tillich. Laplacian eigenvalues and distances between subsets of a manifold. preprint.

[FT99] Joel Friedman and Jean-Pierre Tillich. Calculus on graphs. October 1999.

[GT83] David Gilbarg and Neil S. Trudinger. Elliptic Partial Differential Equations of Second Order. Springer-Verlag, 2nd edition, 1983.

[Hur00] Norman E. Hurt. Mathematical physics of quantum wires and devices. Kluwer Academic Publishers, Dordrecht, 2000. From spectral resonances to Anderson localization.

[KZ01] Peter Kuchment and Hongbiao Zeng. Convergence of spectra of mesoscopic systems collapsing onto a graph. J. Math. Anal. Appl., 258(2):671–700, 2001.

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

[Moh91] Bojan Mohar. Eigenvalues, diameter, and mean distance in graphs. Graphs Combin., 7(1):53–64, 1991.

[RS01] Jacob Rubinstein and Michelle Schatzman. Variational problems on multiply connected thin strips. I. Basic estimates and convergence of the Laplacian spectrum. Arch. Ration. Mech. Anal., 160(4):271–308, 2001.

[Smo83] Joel Smoller. Shock waves and reaction-diffusion equations. Springer-Verlag, New York, 1983.

[Wey12] Hermann Weyl. Der asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichunger. Math. Ann., 71:441–469, 1912.