Graphs, Vectors, and Matrices Daniel A. Spielman Yale University AMS Josiah Willard Gibbs Lecture January 6, 2016 From Applied to Pure Mathematics Algebraic and Spectral Graph Theory Sparsification: approximating graphs by graphs with fewer edges The Kadison-Singer problem A Social Network Graph A Social Network Graph A Social Network Graph “vertex”     or  “node”   “edge”  =     pair of nodes A Social Network Graph “vertex”     or  “node”   “edge”  =     pair of nodes A Big Social Network Graph A Graph G = (V, E) V = vertices, E = edges, pairs of vertices 1   2   3   5   7   11 4   6   9   8   12 10 The Graph of a Mesh Examples of Graphs 1   2   3   5   7   11 4   6   9   8   12 10