Course Information

Instructor: Gary Miller (Office Hours: Tuesday 1-2PM and Thursday 2-3PM )
First Class: Monday September 12th
Place/Time: GHC 4101, MWF 1:30 - 2:50pm. Note Room Change.
Teaching Assistants: Volunteers welcome
Course Secretary: Cleah Schlueter GHC 4113

Announcements

  • Welcome to Spectral Graph Theory. Please take a minute to review the course policies.

Overview

This class will cover material from three areas: Spectral Graph Theory, Numerical Linear Algebra, and the application to problem in CS.

The central issue in spectral graph theory is understanding, estimating, and finding eigenvectors and eigenvalues of graphs. The study of random walks on a graph was one of the first users of spectral graph theory. Answering such questions as: How many times should you shuffle a deck of cards to insure that the deck is "well shuffled"? More recent application include Google's page rank algorithm which performs a random walk on the hyperlink graph of the Internet. It has also been applied to the problem of finding these eigenvectors as well as solving related linear systems.