How to read Spectral Theory of Graphs

Solution 1:

About your reference request, presumably you know Chung's book Spectral Graph Theory. To my knowledge this is the only reference dedicated to spectral methods; however, most major books on graph theory have sections on spectral methods. There seem to be scattered notes on the internet, but I don't know about those.

Edit: the recent book 'Graphs and Matrices' by Bapat is more accessible and has exercises, so it is probably better for self study. I have not read it, but browsing through, it seems like a nice textbook.

Regarding your questions:

1) There are many applications of spectral graph theory in equidistribution theory, additive combinatorics and computer science. Many natural families of graphs can be described by spectral properties and the Laplacian (adjacency matrix) of a graph regulates the behavior of natural dynamical systems on it. For starters read on expander families of graphs (https://en.wikipedia.org/wiki/Expander_graph) and the spectral study of random graphs; also see Qiaochu Yuan's answer in the related question "Motivation for spectral graph theory".

2) That is an interesting question; unfortunately, it is completely open. If $P_n$ is the proportion of graphs on $n$ vertices determined by their spectrum, we don't even know if the limit exists as $n\to \infty$. The conjecture is that $P_n \to 1$, so almost all graphs are determined by their spectra. The fact that such a natural first question is completely open hints at the difficulty of developing a very general 'spectral graph theory' beyond the basics.

3) 'Algebraic graph theory' is even less well-defined that 'spectral'. Following the wikipedia breakdown of algebraic graph theory, the 'linear algebra' of a graph is morally its spectral theory, if you interpret energy estimates, eigenvalue distribution and so on as 'normed algebra'. Group theory is largely concerned with highly symmetric graphs and the interplay between spectral properties and symmetries gives some of the applications mentioned in (1) (namely to equidistribution problems). I don't know much about graph invariants, so I will not comment on that.

4) The real reason why so few books are dedicated to spectral graph theory is that its basics are pretty simple to set up, and beyond that one comes very quickly to the forefront of research (just remember (2)). The research on spectral graph theory usually involves an object from a different research area giving rise to a family of graphs whose spectral properties are interesting, tractable, and relevant for the problem at hand. The accompanying research areas then usually determine the specifics of how spectral theory is to be applied, rather than vice versa. For example, if you are looking at Cayley graphs, it is group theory that dominates the techniques. If you are looking at random graphs, it is probability theory, and so on.

5) Research papers and by studying spectral geometry. Really, as Qiaochu mentioned in the other thread, spectral graph theory is the spectral geometry of the finite metric space given by the word metric of the graph; you first understand the basics of spectral geometry of metric spaces and then spectral graph theory is an instance of that.

Edit: in an answer to a related question (ELI5: What is spectral graph theory?), EHH gave the following link you may also find useful: https://www.youtube.com/watch?v=8XJes6XFjxM