Blyth Lecture Series

History

The R.A. Blyth Lectures are an annual distinguished lecture series in Mathematics and Mathematical Science, established by the Department of Mathematics, University of Toronto on the occasion of the 150th anniversary of the firt Professorship in Mathematics at the University. It consists of three lectures by a distinguished mathematician: the first for a general scientific audience, the second for a general mathematical audience, and the third for specialists in the field.

Information on previous year's events can be found at the following link: http://www.math.toronto.edu/cms/blyth

The 17th Annual Blyth Lecture (September 28 - 30, 2011)

This year the department is proud to welcome Professor Daniel Spielman of Yale University who will present on Laplacian Matrices of Graphs: Applications, Computations, and Approximations

Abstract: I will explain why the Laplacian matrices of graphs are so interesting, how one solves systems of linear equations in these matrices, and how these lead to a notion of what it means for one graph to approximate another. Each talk will be self-contained, although they go best together.

Further details can be found below:

Details

Lecture 3: Sparsification of Graphs and Approximation of Matrices

by Daniel Spielman | Yale University
Time: 15:30 — 17:00  (Friday, Sep. 30, 2011)
Location: BA1130, Bahen Center, 40 St. George St.
Abstract:
A random graph or an expander graph may be viewed as a sparse approximation of the complete graph. We formalize this intuition through a definition of what it means for one graph to be a good spectral approximation of another. This leads us to ask how well a given graph can be approximated by a sparse graph.

The Ramanujan expanders are the best sparse approximations of complete graphs. We prove that every graph can be approximated almost as well by a sparse graph as the complete graphs are by the Ramanujan expanders.

Our algorithms follow from the solution of a problem in linear algebra. Given any expansion of an n-dimensional symmetric matrix A as a sum of rank-1 symmetric matrices, we show that A can be well approximated by a weighted sum of only O(n) of those rank-1 matrices.

Dates in this series

· Wednesday, Sep. 28, 2011: Lecture 1: Spectral and Electrical Graph Theory (Daniel Spielman)
· Thursday, Sep. 29, 2011: Lecture 2: Solving Systems of Linear Equations in Graph Laplacians (Daniel Spielman)
· Friday, Sep. 30, 2011: Lecture 3: Sparsification of Graphs and Approximation of Matrices  (Daniel Spielman)