discrete Laplacian above. Remarkable! Now we’re
beginning to see that this whole graph “Laplacian”
nomenclature has some substance after all, it really
is a discrete analogue of the Laplace operator.
MANIFOLDS OR GRAPHS?
Beyond their operations, there are elegant parallels between the Riemannian manifold setting and the discrete
graph setting for Laplacians. For example, let U ⊂ Rd be
an open, non-empty set and let L2(U) denote the space of
square integrable functions on U . Then the domain of the
Laplace operator D(∆) is the space of smooth, compactly
supported functions on U and dense in L2(U). Then a first
property is the Laplace operator is symmetric on D(∆).
Similarly, the Laplacian L is a symmetric matrix. Another
parallel is the range of the spectra of ∆ and L. On Rn, the
spectrum of ∆ is [0, ∞). Similarly, L has all non-negative real
eigenvalues (that is, it is always positive semidefinite).
According to spectral graph theorist Fan Chung, it is
possible to treat the continuous and discrete cases by a
The general setting is as follows:
1. an underlying space M with a finite measure μ;
2. a well-defined Laplace operator L on functions on M
[a matrix or a graph] so that L is a self-adjoint operator in
L2(M, μ) with a discrete spectrum;
3. if M has a boundary then the boundary condition
should be chosen so that it does not disrupt self-adjointness of L;
4. a distance function dist(x, y) on M so that |∇dist| ≤ 1
for an appropriate notion of gradient. [ 1]
BOUNDARY CONDITIONS AND
HEARING THE SHAPE OF A GRAPH
The spectrum of the continuous Laplace operator gained
due recognition with the famous question posed by Mark
Kac: Can you hear the shape of a drum? The question es-
sentially asked whether drums can be isospectral, or share
eigenvalues. Specifically, let’s model a drum as a mem-
brane stretched and clamped over a boundary, represented
by some domain D in the plane. Let λi be the Dirichlet
eigenvalues, defined by:
−∆u = λu
with the constraint that u = 0 on the boundary of D (con-
sider the membrane from equation ( 2) with a boundary, for
instance). Then these Dirichlet eigenvalues are precisely
the fundamental tones the drum can produce. The ques-
tion, then, is: Given the set of Dirichlet eigenvalues, can we
infer the shape of the drum? That is, do there exist distinct
isospectral domains in the plane?
We can describe a similar problem in the discrete case.
Let G be a graph and S and induced subgraph with
non-empty vertex boundary (the set of vertices not in S
but adjacent to vertices in S). Then we say a function
f: V → R satisfies the Dirichlet boundary condition when
f (v) = 0 for every vertex v in the vertex boundary of S. Then,
for some function f satisfying the Dirichlet boundary
condition, the Dirichlet eigenvalues of G with respect to S
are the λi satisfying:
Lf (v) = λf (v) for every v in S.
Note here L is the normalized Laplacian given by
L = D−½LD−½. Then an analogous question is: Given the set
of Dirichlet eigenvalues, can we infer the shape of S?
It turns out we cannot. The first construction of
isospectral drums in two dimensions was given by Gordon,
Webb, and Wolpert in 1992 [ 2]. Toward the end of the
2000s, Ram Band, Ori Parzanchevski, and Gilad Ben-Shach
gave a construction of isospectral drums and graphs [ 3, 4].
THE NOT-SO-SCARY CONTINUOUS COUSIN
So, as it turns out the “Laplacian” name of our star player
in spectral graph theory is not so arbitrary, and there are
many parallels between the continuous Laplace operator
and the discrete graph Laplacian. As I continue to enrich
my understanding of the connections bet ween the two
cases, I can only hope the power of the Laplace operator
will help me gain intuition about the power of the graph
Laplacian. To conclude, I leave the reader with a few words
from Chung: “For almost every known result in spectral
geometry, a corresponding [question] can be asked: Can
the results be translated to graph theory?” [ 1].
[ 1] Chung, F. Spectral Graph Theory. American Mathematical Society 1996.
[ 2] Band, Parzanchevski, and Ben-Shach. The Isospectral Fruits of Representation
Theory: Quantum graphs and drums. Journal of Physics A Mathematical and
42, 17 (2009).
[ 3] Gordon, Webb, and Wolpert. One Cannot Hear the Shape of a Drum. Bulletin of the
American Mathematical Society 27 (1992), 134-138.
[ 4] Parzanchevski and Band. Linear Representations and Isospectrality with Boundary
Conditions. J. Geometric Analysis
20, 2 (2010), 439.
Olivia Simpson is a Ph. D. student at UCSD. When she's not busy with research in
graph theory and theoretical computer science, she enjoys spending her time on
the beaches and mountains of Southern California.
Nicaraguan Sign Language (NSL) developed spontaneously
amongst hearing-impared students in rural Managua, the
emergence of this nascent language intrigues linguists because
NSL follows the “universal grammar” shared by all languages.