Spectral sparsification
by John from John D. Cook on (#3PY3J)
The latest episode of My Favorite theorem features John Urschel, former offensive lineman for the Baltimore Ravens and current math graduate student. His favorite theorem is a result on graph approximation: for every weighted graph, no matter how densely connected, it is possible to find a sparse graph whose Laplacian approximates that of the original graph. For details see Spectral Sparsification of Graphs by Dan Spielman and Shang-Hua Teng.
You could view this theorem as a positive result-it's possible to find good sparse approximations-or a negative result-the Laplacian doesn't capture very well how densely a graph is connected.
Related: Blog posts based on my interview with Dan Spielman at the 2014 Heidelberg Laureate Forum.