Math 262 Lecture Notes
Back to Mary's Homepage
To Math 262 Homepage
For exercises accompanying these lectures, please see Andy Parrish's site.
- Lecture 1: 30 March 2009. Course introduction and overview.
- Lecture 2: 1 April 2009. Definitions of combinatorial and normalized Laplacian matrices and spectrum. A homological perspective on spectral graph theory. The Matrix-Tree Theorem.
Resources:
- Lecture 3: 6 April 2009. Laplacian spectrum from the perspective of potential functions, Rayleigh quotients, harmonic eigenvectors.
Resources:
- Lecture 4: 8 April 2009. Introduction to electrical networks: resistance, conductance, current, voltage. Kirchhoff's Current Law and Voltage Law. Induced current.
Resources:
- Lecture Notes, thanks to Jake Hughes.
- Much of the material in this lecture can be found in Béla Bollobás' Modern Graph Theory.
- Lecture 5: 13 April 2009. Introduction to electrical networks, continued: Uniqueness of current, Forest-tree thm. Some bounds on λ1.
Resources:
- Lecture Notes, thanks to Franklin Kenter.
- The material regarding electrical networks can be found in Béla Bollobás' Modern Graph Theory.
-
Chapter 1 of Spectral Graph Theory contains the bounds we established for the spectral gap.
- Lecture 6: 15 April 2009. Upper and lower bounds on λ1: Alon-Boppana bound, bounds using average degree and chromatic number.
Resources:
- Lecture 7: 20 April 2009. A proof of the bound on λ1 using chromatic number, introduction of the Cheeger constant; the Cheeger Inequality.
Resources:
- Lecture 8: 22 April 2009. Continued proof of the Cheeger Inequality, bounds on λ1 for edge-transitive graphs.
Resources:
- Lecture 9: 27 April 2009. An alternate proof of the bound on λ1 for regular edge-transitive graphs, introduction to random walks.
Resources:
- Lecture Notes: a work in progress. Please be patient.
- Chapter 7 of Spectral Graph Theory contains the results related to edge-transitive graphs.
- Lecture 10: 29 April 2009. Convergence of a (lazy) random walk to the stationary distribution: Total variation distance, relative pointwise distance, χ-Squared distance. Localized Cheeger constants.
Resources:
- Lecture 11: 4 May 2009. Localized Cheeger constants; a bound on the distance between the kth step of the lazy random walk and the stationary distribution.
Resources:
- Lecture 12: 11 May 2009. Quasi-random graph properties; the discrepancy inequality.
Resources:
- Lecture 13: 13 May 2009. The discrepancy and eigenvalue properties and uses. An eigenvalue bound on the diameter of a graph.
Resources:
- Lecture 14: 18 May 2009. The discrepancy and eigenvalue properties and uses; quasi-random properties and their equivalence.
Resources:
- Lecture 15: 20 May 2009. Eigenvalues of random graphs; Perron-Frobenius theory and Interlacing. G(w) model of random graphs.
Resources:
- Chapter 5 of Complex Graphs and Networks.
- For Perron-Frobenius theory and other linear algebra type results: Chapter 8 of Matrix Analysis by Horn and Johnson.
- Lecture 16: 27 May 2009. Lovasz Local Lemma: various versions, applications to diagonal Ramsey numbers.
Resources:
- Lecture 8 of Ten Lectures on the Probabilistic Method by Spencer.
- Section 5.1 of The Probabilistic Method by Alon and Spencer.
- Moser and Tardos' paper can be found here.
- Lecture 17: 1 June 2009. Lovasz Local Lemma: general form and algorithmic proof (due to Moser and Tardos).
Resources:
- Moser and Tardos' paper can be found here.
- Spencer's note on Moser and Tardos' proof can be found here.
- Lecture 18: 3 June 2009. Fan's map of the combinatorics landscape (see here.)
The template for lecture notes can be found here. If you have anything to add to the resources here, would like the original tex file for a set of notes, or need me to post your notes from lecture, please email me at mradcliffe@math.ucsd.edu .