T-79.7001 Postgraduate Course in Theoretical Computer Science (2–10 cr)
Spectral graph theory investigates properties of graphs
via the linear algebraic characteristics of their adjacency matrices.
This deep area of discrete mathematics has been
the source of many significant algorithmic advances in recent
years (rapidly mixing Markov chains, expander graphs for
derandomisation, methods for the analysis of large
nonuniform networks, etc.)
The goal of the graduate TCS seminar this semester will
be to achieve a working understanding of this fascinating topic
by studying some well-known textbooks chapter by chapter.
The course T-79.7001 replaces the course
T-79.300 Postgraduate Course in Theoretical Computer Science
- [25 Jan 2006] Several changes in the seminar arrangements,
following discussions at the first session. Note also that
as of 30 Jan, the sessions start at 4:30.
- [3 Jan 2006] The first seminar session is on Mon 23 Jan.
- Time, place: Mondays 4:30-7 p.m.,
seminar room TB353.
- Registration by
- Prerequisites: Basic knowledge of probability
theory, linear algebra and discrete mathematics.
- Assets: Familiarity with stochastic processes,
- Credits: 1.5 cr (ECTS) per moderated session,
1 cr (ECTS) per each 10 problems solved (incl. attendance
at the respective sessions).
- Grading: Based on the quality of discussion at
the moderated session and the quality of the submitted
||Topic (D&S section numbers refer to the
||Opening, overview, handing out assigments
Random walks and electric networks (Doyle & Snell 1.1)
||1.1.2, 1.1.5, 1.1.6, 1.1.9
||Random walks in two dimensions (Doyle & Snell 1.2)
||1.2.2, 1.2.5, 1.2.6, 1.2.9
||Random walks on finite networks (Doyle & Snell 1.3.1-1.3.4)
||1.3.3, 1.3.4, 1.3.8, 1.3.10
||Thomson's principle and Rayleigh's monotonicity law
(Doyle & Snell 1.3.5, 1.4)
||1.3.11, 1.3.12, 1.4.10, 1.4.11
||Random walks on infinite networks (Doyle & Snell 2.1-2.2)
||2.1.5, 2.1.6, 2.2.3, 2.2.5
||The spectrum of a graph;
regular graphs and line graphs (Biggs 2-3)
||Cycles and cuts;
spanning trees and associated structures (Biggs 4-5)
determinant expansions (Biggs 6-7)
||Vertex-partitions and the spectrum (Biggs 8)
||Laplacians and eigenvalues (Chung 1.1-1.4)
||Eigenvalues and random walks (Chung 1.5)
||Easter vacation: no seminar.
||The Cheeger constant and edge expansion (Chung 2.1-2.3)
||Satu Elisa Schaeffer
|18.|| 1 May
||Vappu: no seminar.
- The seminar sessions comprise two parts: a discussion
section on the relevant background theory, and
a problem-solving session covering four pre-selected
- The participants are responsible for moderating the
discussion sections according to the schedule above.
This includes outlining the main results
and ideas in the material and working out unclear points
in collaboration with the other participants.
- Each week's moderator should choose/make up four reasonable
problems on the material he/she covers, and announce these
to the other participants at the end of the preceding week's
seminar session. He/she is then also in charge of running the
problem-solving session covering these problems. This
includes having solutions to the problems in case no one else
has been able to work them out.
- Solution sets are collected from all participants at the
end of each week's session. These are used as the basis
for assigning credit and grading of the seminar.
- The moderator can mail copies of any slides he/she may have used,
together with any possible additional literature pointers,
to the coordinator after the presentation.
These will then be linked to the schedule above.
- N. Biggs,
Algebraic Graph Theory, 2nd Ed.
Cambridge University Press, 1993.
- F. R. K. Chung,
Spectral Graph Theory.
American Mathematical Society, Providence RI, 1997.
(First chapter available online
- P. G. Doyle, J. L. Snell,
Random Walks and Electric Networks.
Mathematical Association of America, Washington DC, 1984.
- D. M. Cvetkovic, M. Doob, H. Sachs,
Spectra of Graphs, 3rd Ed.
J. A. Barth Verlag, Heidelberg, 1995.
- C. Godsil, G. Royle,
Algebraic Graph Theory.
Springer-Verlag, New York NY, 2001.
Latest update: 24 April 2006.