Post by Mark Dominus

11h

I did Google search just now for Padraic Bartlett's excellent lecture notes on spectral graph theory, and discovered that most of the top hits were for my web site, where I had archived them after last time I went looking for them, apparently in 2011. Perhaps foreseeing exactly this moment.

Spectral graph theory is wild. It treats graph adjacency matrices as actual _matrices_ and asks what you can learn about the graph from studying the eigenvalues of the matrix and such like.

If someone had asked me about this before I knew the answer, I would have guessed that there was pretty much nothing you could extract from the eigenvalues of the adjacency matrix. But the opposite is true.

https://www.plover.com/misc/math/Spectral%20Graph%20Theory/

Edited 11h ago

3 0 1 View Post & Replies See Original

8h

Here's a very elementary example. Let G be a graph with adjacency matrix A. Then the number of distinct triangles in G is equal to

tr(A³)/6

where tr() is the trace.

0 0 0 View Post & Replies See Original

7h

@mjd - it's a cool subject. I know only a bit - I know more about the related subject of graph Laplacians and how they're connected to electrical circuits and the theory of "topological crystals". Here's a free open-access book on spectral graph theory that I just bumped into, looking around, right now:

https://link.springer.com/book/10.1007/978-3-662-67872-5

0 0 0 View Post & Replies See Original

6h

@mjd Thanks for sharing this! I [am very lucky to] teach a year-long high school linear algebra course, and we mix in graph theory along the way. The fact that the all-1s vector is an eigenvector of the graph Laplacian is an awe-inspiring "ah ha!" moment in the spring!

Every year multiple students gravitate toward spectral graph theory for their end-of-year projects, and I'm excited to have another quality resource to share with them. Thanks!

0 0 0 View Post & Replies See Original