I’m at this talk by Dan Spielman of Yale University, who’s trying to give us an introduction to spectral and algebraic graph theory. I’m here because he was my friend’s undergraduate advisor and my friend said that “Professor Dan” is great! Dan has won a ton of fancy prizes and there are so many people in the audience to watch him.
This talk wove together computer science, graph theory, physics in a very engaging manner. It was a lot of fun, and any errors in this blog post are mine alone, which is embarrassing because I should know a fair amount of spectral graph theory and group theory (I even did my senior math seminar at Yale in spectral graph theory in 2010. Woof.)
In spectral graph theory, we relate graphs to matrices. The first example is an adjacency matrix , where you label the vertices of a graph and then use those labels as row/column labels for a square matrix, and put a “0” when there is no edge between the corresponding vertices, and a “1” if there is such an edge.
Dan: “I think it’s an accident that the adjacency matrix is useful.” He’ll go on to talk about associated matrices, linear equations, quadratic forms, and operators that are less accidental.
Quadratic forms give us some beautiful theorems about graphs.