Spectral Graph Theory Lecture 4 Bounding Eigenvalues

These notes are not necessarily an accurate representation of what happened in class. The notes written before class say what I think I should say. I sometimes edit the notes after class to make them way what I wish I had said. There may be small mistakes, so I recommend that you check any mathematically precise statement before using it in your own work. These notes were last revised on September 22, 2015. 4.1 Overview It is unusual when one can actually explicitly determine the eigenvalues of a graph. Usually one is only able to prove loose bounds on some eigenvalues. In this lecture, I will introduce two important techniques for proving such bounds. The first is the Courant-Fischer Theorem, which provides a more powerful characterization of eigenvalues as solutions to optimization problems than the one we derived before. This theorem is useful for doing things like proving upper bounds on the largest eigenvalue of a matrix. The more powerful technique we will see allows one to compare one graph with another, and prove things like lower bounds on the largest eigenvalue of a matrix. It often goes by the name “Poincaré Inequalities ” (see [DS91, SJ89, GLM99]), although I often use the name “Graphic inequlities”, as I see them as providing inequalities between graphs. 4.2 The Courant-Fischer Theorem I gave a hint of the Courant-Fischer Theorem earlier in the semester. I’ll do the rest of it now. Theorem 4.2.1 (Courant-Fischer Theorem). Let L be a symmetric matrix with eigenvalues λ1 ≤ λ2 ≤ · · · ≤ λn. Then, λk = mi