Spectral Graph Theory Lecture 17 Sparsification by Effective Resistance Sampling

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 November 3, 2015. 17.1 Overview I am going to prove that every graph on n vertices has an -approximation with only O(−2n log n) edges (a result of myself and Srivastava [SS11]). We will prove this using a matrix Chernoff bound due to Tropp [Tro12]. We originally proved this theorem using a concentration bound of Rudelson [Rud99]. This required an argument that used sampling with replacement. When I taught this result in 2012, I asked if one could avoid sampling with replacement. Nick Harvey pointed out to me the argument that avoids replacement that I am presenting today. 17.2 Sparsification For this lecture, I define a graph H to be an -approximation of a graph G if (1 − )LG 4 LH 4 (1 + )LG. We will show that every graph G has a good approximation by a sparse graph. This is a very strong statement, as graphs that approximate each other have a lot in common. For example, 1. the effective resistance between all pairs of vertices are similar in the two graphs, 2. the eigenvalues of the graphs are similar, 3. the boundaries of all sets are similar, as these are given by χTSLGχS, an