MATH 264 Spring 2011 Lecture Schedule and Notes
This website is maintained by Franklin Kenter who can be contacted by email
fkenter (AT-AT) math (dot.dot) ucsd (dotty) edu
Starting the 3rd week or so, each class session will be organized as follows:
For the first 50 minutes there will be a lecture by Professor Fan Chung followed by a student presentation for the remaining 30 minuntes. Each student enrolled in the course is expected to give at least one presentation. To sign up for a presentation, please email your topic and preferred date to Franklin Kenter (email above). Presentation topics and dates will be allocated on a first come, first served basis.
For your presentation, either shortly before or after, please submit a short write-up of your presentation (e.g., the theorems and relevant proofs or proof sketches) along with a list of references (e.g. the papers on which you are basing your presentation).
In addition, we will take turns writing up the lecture notes for the lecture portion of the class. A LaTeX template for notes can be found here: here. (Thank's Mary)
Each lecture, a couple of exercises, problems, research problems, and open problems are briefly posed. Mary (thanks again) has compiled a list of all such brain-teasers here.
(March 29) Lecture 1: Overview, course description, list of topics, and applications of spectral graph theory.
(March 31) Lecture 2: Random walks and the transition probability matrix and norms over random walks.
(April 5) Lecture 3:
(April 5) Lecture π: Immediately after the (slightly-shortened) third lecture, there is a very special lecture, the Kyoto prize symposium, given by by László Lovász. You are strongly encouraged to attend the symposium. Registration is necessary, but I have registered enough spaces for the entire class.
Time: 3:30 - 5:00 PM
Venue: UCSD, Price Center Ballrooms A & B
(April 7) Lecture 7/2: In addition to the Kyoto prize symposium, László Lovász will be giving a more technical presentation in the mathematics department.
Title: General questions about extremal graphs
Time: 11:00 AM
Venue: Natural Sciences Building Auditorium
(This venue is small, please arrive early).
(April 7) Lecture 4: Upper Bounds for Random Walk Convergence
(April 12) Lecture 5: Electrical Networks and (s,t)-flow
Student Presenter and Topic: Craig Timmons on “Spectral Methods in Extremal Graph Theory”
Notes, Exercises, and Problems from Criag's presentation
(April 14) Lecture 6:
Student Presenter and Topic: James Pascoe on “Vibrational Spectrum of Geometrical Graphs”
Notes from James' presentation
(April 19) Lecture 7: Cheeger constant and its L1 characterization.
Student Presenter and Topic: Franklin Kenter on “Discrepancy Inequalities for Directed Graphs”
(April 21) Lecture 8: Guest Lecturer: Steve Butler on “Constructions of Cospectral Graphs”
(April 26) Lecture 9: Expander Graphs, Part I... Notes written by Andy Parrish
Student Presenter and Topic: Mary Radcliffe on “The Spectrum and Hamiltonicity of Graphs”
Mary Radcliffe's Notes on her presentation
(April 28) Lecture 10: Expander Graphs, Part II... Notes written by Andy Parrish
Student Presenter and Topic: Andy Wilson on “The Lovász Theta Function”
Andy Wilson's Slides (Exercizes and References therein)
(May 3) Lecture 11: Lovasz' Theta Function and the Sigma Function
Student Presenter and Topic: Jake Hughes on “Matchings in Regular Graphs”
Jake Hughes' Slides (Exercises and References therein)
(May 5) Lecture 12: Error-Correcting Codes Part I
Student Presenter and Topic: Mark Kempton on “Expander Graphs”
(May 10) Lecture 13: Error-Correcting Codes Part II
Student Presenter and Topic: Andy Parrish on “Explicit Constructions of Small Folkman Graphs”
Andy Parrish's notes (Exercises, Questions, and References therein)
(May 12) Lecture 14: Expander Graphs
Student Presenter and Topic: Craig Timmons on “Finding Cliques in Random Graph”
Craig Timmons' Slides (References therein)
(May 17) Lecture 15: Matrix-Forest Theorem
Student Presenter and Topic: Mary Radcliffe on “Spectra of General Random Graphs”
Mary Radcliffe's Slides (References therein)
(May 19) Lecture 16: The Zeta Function on Graphs and its Relation to the Matrix-Tree Theorem.
Student Presenter and Topic: Stephen Young on “Braess's Paradox and Expanders”
Roughgarden's Paper on Braess's Paradox: http://theory.stanford.edu/~tim/papers/nd_hard.pdf
Valiant and Roughgarden paper on Braess's Paradox in Random Graphs: http://theory.stanford.edu/~tim/papers/rbp.pdf
(May 24) Lecture 17: Decomposing Graphs and Hypergraphs into Complete Bipartite Graphs and Its Applications.
Guest Lecture: Jacques Verstraete
… Notes Written by Franklin Kenter
(May 26) Lecture 18: Covering Graphs and Hypergraphs with Cliques
Guest Lecture: Jacques Verstraete
(May 31) Lecture 19: Graph Coverings and Eigenvalues, Part I
Student Presenter and Topic: Franklin Kenter on “Spectral Conditions for the Weak-Coloring of Hypergraphs”
(June 2) Lecture 20: Graph Coverings and Eigenvalues, Part II
Student Presenter and Topic: