Spectral Graph Theory – Visiting and Early Research Scholar's Experiences in Mathematics (VERSEIM-REU)

Directed by Fulton Gonzalez

Spectral Graph Theory is the study of the properties of a graph through the properties of the eigenvalues and eigenvectors of matrices 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, and 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 one possible extension: the relation of graph Laplacians with mean value operators and group theory.

Let $X$ be a simple graph, which can have either finite or infinitely many vertices. (By simple, we mean that the edges of $X$ are undirected, there is no more than one edge between two vertices, and no edge starts and ends at the same point.) Consider the following sample graph:

Let us order its vertices and edges. This order can be arbitrary, and the purpose is to assign rows and columns to the matrices we’ll define. For example, in the sample graph above, our vertices are ordered $V_1,V_2,V_3,V_4,V_5$ , and our edges are ordered $1,2,3,4,5,6$ . Next, to our graph we associate three matrices: the adjacency matrix $A$ , the degree matrix $D$ , and the incidence matrix $S$ .

The adjacency matrix of $X$ is a symmetric square matrix whose rows and columns correspond to the vertices of our graph, and where the $(i,j)$ entry is $1$ if vertex $V_i$ and vertex $V_j$ are joined by an edge, and is $0$ otherwise. Here is the adjacency matrix of our sample graph:

The degree matrix $X$ is a diagonal matrix whose rows and columns correspond to the vertices of our graph, and whose $(i,i)$ -entry is the degree of the vertex $V_i$ : this is the number of edges emanating from the vertex $V_i$ . For our sample graph, the degree matrix is

Finally, the incidence matrix $S$ of $X$ is a matrix whose rows correspond to the edges of $X$ and whose columns correspond to the vertices of $X$ . The entries of $S$ are given as follows. Suppose that edge $i$ has endpoints $V_j$ and $V_k$ , with $j<k$ . Then

$s_{il}=\begin{cases} +1&\text{ if }l=j\ -1&\text{ if }l=k\ 0&\text{ if }l\neq j\text{ or }k \end{cases}$

Thus for our sample graph above, the incidence matrix is

If $n$ is the number of vertices of $X$ , then the graph Laplacian of $X$ is the $n\times n$ matrix

$L=S^T S.$

It is easy to show that $S^T S=D-A$ . This is the simplest Laplacian that can be associated with a graph. There are other types of graph Laplacians, such as Markov Laplacians, symmetric normalized Laplacians, and random walk normalized Laplacians. These are all defined in terms of the matrices $A$ and $D$ .

The graph Laplacian $L$ is singular and has nonnegative eigenvalues. Thus $0$ is always an eigenvalue, and the column matrix

If a graph $X$ has vertex set $V={V_1,V_2,\ldots,V_n}$ , then a function on $V$ can be identified with an $n\times 1$ column vector

Here $f_1=f(V_1),\ldots,f_n=f(V_n)$ . A function $f$ on $V$ is called harmonic if $Lf=0$ .

There has been a lot of recent interest in graph Laplacians, and their associated eigenvalues and eigenvectors, due to their relation with the large scale geometries of graphs as well as their applications to, for example, data science. They are the natural discrete analogues of the Laplace operator in $\mathbb R^n$ :

$\Delta=\frac{\partial^2}{\partial x_1^2}+\frac{\partial^2}{\partial x_2^2}+\cdots+\frac{\partial^2}{\partial x_n^2}.$

Graph Laplacians share several of the properties of the Euclidean Laplacian. The goal of this project is to study some further analogues to Euclidean Laplacians, such as mean value properties, which are obvious at distance $1$ , but which don’t hold at larger distances unless additional regularities are present in a graph.

desired background

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.