Spectral Graph Theory
Math 535 - Topics in Combinatorics
Fall 2005
room |
meeting times |
Cupples I - 215 |
Mon Wed Fri 3:00 AM - 4:00 PM |
instructor |
phone # |
office |
e-mail |
office hours |
Renato Feres |
5-6752 |
Cupples I 17 |
feres@math.wustl.edu
|
TuTh 1:00 PM - 2:30 PM |
Note: You can see me outside the set office hours, but contact me in advance
to be sure I'm in.
This is an introduction to graph theory with emphasis on analytical and probabilistic
questions. Some familiarity with concepts in algebra, mainly linear algebra and group theory, will be necessary, as well
as acquaintance with basic concepts in probability theory.
Topics: We plan to cover the following main topics.
- Generalities about graphs;
-
The Laplacian of a weighted graph, harmonic functions, Harnack inequalities;
- Random walks on graphs and groups and the correspondence between
random walks and electrical networks;
-
Isoperimetrical problems, diameters and eigenvalues;
- Expanders;
- Spectrum of symmetrical graphs and group representations;
- Boundary value problems (Neumann and Dirichlet eigenvalues);
- Heat kernels, logarithmic Sobolev inequalities, and more random walks.
Grades will be based on a (moderate) amount of homework assignments, or a presentation on
a topic related to the course subject of the student's choosing.
Texts: Some of the sources we plan to use:
-
Spectral Graph Theory by Fan R. K. Chung (CBMS Regional Conference Series in Mathematics, number 92 - AMS, 1997).
This is probably going to be our main text. Other sources will be used to enliven it a bit.
-
Modern Graph Theory by Bela Bollobas, Springer-Verlag, 1998.
-
Elementary Number Theory, Group Theory, and Ramanujan Graphs by G. Davidoff, P. Sarnak, A. Valette - London
Mathematical Society, Student Texts 55, Cambridge University Press, 2003.
-
Spectres de Graphes by Yves Colin de Verdiere. Cours Specialises, collection SMF, numero 4, 1998 (distributed by the AMS).
-
Random Walks on Infinite Graphs and Groups by Wolfgang Woess. Cambridge Tracts in Mathematics, number 138, Cambridge University
Press, 2000.
- Graph Theory by Reinhard Diestel. Springer-Verlag, electronic edition, 1997, 2000. (
Free download)