Spectral graph theory and differential equations – Visiting and Early Research Scholar's Experiences in Mathematics (VERSEIM-REU)

Spectral graph theory and differential equations

Spectral Graph Theory is the study of the properties of a graph through the properties of functions, matrices, and other objects associated with the graph, most importantly the graph Laplacian and its variants. Numerous papers have appeared in the recent literature on
this subject, especially since it has powerful and wide-ranging applications, such as in data mining, clustering, segmentation, shape matching and recognition, and even differential geometry.

There are many theorems in the spectral theory of partial differential operators that turn out to have counterparts in spectral graph theory, and this project will focus on the exploration of the graph Laplacian and the wave equation with mean value operators on homogeneous trees.

Fix a positive integer $q$ . A homogeneous tree of degree $q+1$ is a tree (i.e., an undirected graph without cycles) such that every vertex has degree $q+1$ . It is easy to see that any such tree has infinitely many vertices. If $q=1$ , we can identify the tree with the set of integers $\mathbb Z$ .

In particular, one can study the counterparts of certain differential equations on $\mathbb R^n$ to see how the solutions behave on homogeneous trees. Since trees (and graphs) are discrete objects, differential equations on trees take on the form of difference equations on the vertices and edges.

Here are a couple of examples. Let $T$ be a homogeneous tree of degree $q+1$ , let $V$ be its set of vertices, and suppose that $f$ is a function on $V$ . The Laplacian of $f$ is the function $Lf$ on $V$ given by

$Lf(v)=f(v)-\frac{1}{q+1}\,\sum_{d(w,v)=1} f(w),$

for any vertex $v\in V$ . In the right-hand side above, we subtract from $f(v)$ the average of $f$ on all the vertices adjacent to $v$ . The expression $d(v,w)$ denotes the distance from $v$ to $w$ , meaning the length of the shortest path in $T$ from $v$ to $w$ . (Such a path is unique.)

A function $f$ on $V$ is said to be harmonic if it satisfies Laplace’s equation $Lf=0$ . If $f$ is harmonic, then $f(v)$ is the average of $f$ on the neighbors of $v$ , and it is easy to show that $f(v)$ is also the average of $f$ on all the vertices at a fixed distance from $v$ . This is the mean value property of harmonic functions, which in $\mathbb R^n$ is one of the defining features of harmonic functions.

Another example is the wave equation on $T$ . Suppose that $f$ is a function on $\mathbb Z\times V$ . We write $f(k,v)$ as $f_k(v)$ , for $k\in\mathbb Z$ and $v\in V$ . (Think of $f(k,v)$ as a function on the set of vertices $V$ which takes on differing values at time $k=\ldots,-2,-1,0,1,2,\ldots$ .) We say that $f(k,v)$ satisfies the wave equation if

$L f_k(v)=\frac{1}{2} f_{k+1}(v)+\frac{1}{2} f_{k-1}(v)- f_k(v)$

for all $k,\,v$ .

If we are given the “initial” values $f_0$ and $f_1$ , there are ways to obtain closed form explicit solution for $f_k$ , for all $k$ .
This project aims to find a different explicit solution to the wave equation using a technique called Asgeirsson’s Mean Value Theorem.

The prerequisite for successful participation in this project is a solid background in multivariable calculus and linear algebra, as well as some familiarity with theorem-proving.