Lecture notes for a series of three talks given by Steve Butler at the Center for Combinatorics at Nankai University, Tianjin, China in September 2006.
| Three common spectra | In this first talk we will introduce three of the most commonly used types of matrices in spectral graph theory. They are the adjacency matrix, the combinatorial Laplacian, and the normalized Laplacian. We also will give some simple examples of how the spectrum can be used for each of these types. |
|---|---|
| Applications of Courant-Fischer | In this second talk we will introduce the Rayleigh quotient and the Courant-Fischer Theorem and give some applications for the normalized Laplacian. Our applications will include structural characterizations of the graph, interlacing results for addition or removal of subgraphs, and interlacing for weak coverings. We also will introduce the idea of "weighted graphs". |
| Cheeger constants and discrepancy | In this third talk we will discuss properties related to edge expansion. In particular, we will define the Cheeger constant (which measures how easy it is to cut off a large piece of the graph) and state the Cheeger inequalities. We also will define and discuss discrepancy for undirected and directed graphs. We also state the Perron-Frobenius Theorem which is a useful tool in spectral graph theory, particularly for directed graphs. |
The material these lectures are based on comes primarily from the work of Fan Chung, and in particular her book Spectral Graph Theory (the first four chapters of which are available online), as well as some personal research into interlacing and discrepancy. For more information please feel free to contact Steve Butler.