Beauty of Spectral Graph Theory 
*

*Why would one choose to study spectral graph theory?

*Where can the spectrum of complete graphs, for example, be applied in real- life example or of any graph in general?

*A brief historical background of spectral graph theory

*What is beautiful about this result?


I'm interested in all these questions to find the purpose of spectral graph theory
 A: I'm an undergraduate student doing academic research in spectral graph theory.
I ended up doing spectral graph theory because I didn't have any particular interest when I approached my current mentor about working under him. His area of research is focused on graph theory and combinatorics, and he introduced me to some of his work. When I finished, he presented me some open questions related to his latest publication and I decided to work in spectral graph theory.
I'll give a few applications of spectral graph theory that have come up in my research. First, the spectral partitioning algorithm and algebraic connectivity. If $G$ is a connected graph, the second smallest eigenvalue of the laplacian matrix, called the Fiedler eigenvalue or algebraic connectivity, is related to the connectivity of the graph. The positive and negative entries of the eigenvector corresponding to this eigenvalue create an almost equitable partition on the vertex set of the graph.
There is also the spectral positioning algorithm. If $x_1, x_2, x_3$ are the eigenvectors corresponding to the three smallest nonzero eigenvalues of the graph laplacian, the $(x, y, z)$ coordinate of the $i$-th vertex of $G$ is given by the $i$-th entries of $x_1, x_2$, and $x_3$, respectively. I created a graph plotting library that used spectral positioning to do most of the heavy lifting, so it does come in useful.
More relevant to my research, the minors of the laplacian matrix count the number of unique spanning trees and spanning forests of a graph. I study the resistance distance, which is a graph distance metric characterized as
$$\begin{equation*}
    r_G(i, j) = \frac{\mathcal F_G(i, j)}{T(G)},
\end{equation*}$$
where $\mathcal F_G(i, j)$ is the number of spanning forests separating $i, j \in V(G)$ and $T(G)$ is the number of spanning trees in $G$.
My current work is focused on Kemeny's constant, an invariant of Markov chains. The Kemeny's constant of a simple connected graph $G$ is given by the weighted sum
$$\begin{equation*}
    \mathcal K(G) = \sum_{i, j \in G} \frac{d_i d_j r_G(i, j)}{4m},
\end{equation*}$$
where $m$ is the number of edges in the graph and $d_i$ is the degree of the $i$-th vertex. This constant is another way to describe graph connectivity, characterized by the expected number of transitions to reach any vertex in the graph, independent of the starting point. A large Kemeny's constant corresponds to a poorly connected graph, and a small Kemeny's constant to a well-connected one.
A real-life application of Kemeny's constant is Braess' paradox in traffic planning; Braess was able to show that there exist graphs such that adding edges between certain vertices would result in an increase of Kemeny's constant. Counterintuitively, graphs with more edges may be poorly connected compared to less dense graphs. Braess used this result to improve traffic networks and building plans for hospitals.
I know very little of the history of spectral graph theory, but the pioneers in my area of research include John Kemeny, J. Snell, and Ravindra Bapat. More recently, Jane Breen, Lorenzo Ciardo, and Steve Kirkland have authored and co-authored many interesting results that I frequently refer to.
To me, spectral graph theory is a beautiful discipline because of the structure and order of graphs. The way that graph spectra capture so many of the interesting properties and invariants of graphs is an intriguing connection. Most results require extensive eigenvalue computations or formula manipulation, which makes discovering a new connection very rewarding.
