390036 UK VGSCO Spectral Graph Theory and Algorithms (2017S)

We will give an overview of the surprising connection between the eigenvalues and eigenvectors of graphs expressed as matrices, and classical questions in graph theory, such as bipartiteness, planarity, cliques, colorings, cuts, flows, paths, and walks. Both older structural results and recent algorithmic results will be presented. Topics to be covered include the matrix-tree theorem, Cheeger's inequality, Trevisan's max cut algorithm, bounds on random walks, Laplacian solvers, electrical flow and its applications to max flow.