2
$\begingroup$

I was wondering how did Spectral graph theory, this multidisciplinary area between Linear Algebra and Graph theory start?

How did it emerge?

Was there a certain problem (maybe graph isomorphism problem?) that evoked its formation?

$\endgroup$
  • $\begingroup$ Perhaps math history tag is appropriate here? $\endgroup$ – Yanko Sep 21 '18 at 13:34
  • 3
    $\begingroup$ Once the idea of writing down the adjacency matrix is born, it isn't at all hard to use linear algebra to analyse the property of this matrix (and others). Also, the problem of random walk on (possibly directed) graphs are already out there and there too you have all these tools already being used. In a sense, it is just a matter of pulling these together and give it a coherent theory. $\endgroup$ – user10354138 Sep 21 '18 at 14:02
4
$\begingroup$

The oldest work on spectral graph theory that I am aware of is the work by chemists on Hueckel molecular orbital theory (https://en.wikipedia.org/wiki/Hückel_method). One principal goal of this work was to relate chemical properties of aromatic hydrocarbons to spectral properties of the underlying graphs. The work of Coulson was very influential.

Chemists also studied the matching polynomial before graph theorists became interested in the topic. (I view the matching polynomial as a topic in spectral graph theory.)

Another starting point would be the original paper by Hoffman and Singleton on Moore graphs. It seems hard to overestimate the significance of this work. One thing it did was establish the connection between problems in extremal graph theory and graph spectra.

Certainly there was always the hope that one might use spectral information for graph isomorphism but it does not appear that lead to the development of spectral graph theory.

$\endgroup$
0
$\begingroup$

Well for one thing, certain combinatorial properties of a graph that are of interest to graph theorists and theoretical computer scientists, can be gleaned from analysing the adjacency matrix of the graph. For example, (put informally) a $k$-regular graph $G$ (where $k \ge 3$) is an expander (i.e., lots of edges between $S$ and $V(G) \setminus S$ for arbitrary nonempty subsets $S$ of $V(G)$) iff every eigenvalue except the largest is less than $(1-\epsilon)k$.

Surely there are other interesting combinatorial properties of a graph that can be gleaned from its adjacency matrix, but this comes to mind to me now.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.