8
$\begingroup$

My background is a course is

  1. Linear Algebra -Hoffman,Kunze
  2. Graph Theory-Frank Harary

I am doing a coursework in Spectral Graph Theory .

As I am going through it, I am searching for some applications in this topic.

  • One application I found was showing two graphs are non-isomorphic . If the Laplacian Matrix of two graphs have different spectrum then the graphs are non-isomorphic.
  • Are there any other?
  • What is the probability that if two graphs are cospectral then they are isomorphic?
  • Is Algebraic Graph Theory different from Spectral Graph Theory or one is a branch of the other?
  • Why are no books available on Spectral Graph theory barring a few while there are plenty on other topics?
  • How do people study in this topic?

If anybody can find a suitable answer to these questions then I would be extremely grateful.

$\endgroup$
  • $\begingroup$ For an application, see my answer here, which describes "spectral realizations" of graphs. $\endgroup$ – Blue May 15 '16 at 19:35
8
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That's a nice and detailed answer ,so which book do you recommend starting with $\endgroup$ – Learnmore May 16 '16 at 2:36
  • $\begingroup$ Are you also involved in this field $\endgroup$ – Learnmore May 16 '16 at 2:36
  • $\begingroup$ @learnmore Chung's book is the standard recommendation, there is no other accessible reference (that I know of). As for me, I am using spectral graph theory in applications in equidistribution. For an introduction to the circle of problems I am interested in see Lubotzky's Discrete groups, Expanding Graphs and Invariant Measures. I would mention it in the answer, but it is far too advanced given your stated background. $\endgroup$ – guest May 16 '16 at 3:59
  • $\begingroup$ @learnmore I see now that there is a new book called 'graphs and matrices' by Bapat. This may be more accessible than Chung, give it a try. $\endgroup$ – guest May 16 '16 at 4:05
  • $\begingroup$ but there aren't any exercises in Chung ;How can I make sure that what I have learnt is correct $\endgroup$ – Learnmore May 16 '16 at 4:05

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.