|
T-79.7001 Postgraduate Course in Theoretical Computer Science (2–10 cr)
P V
Spring 2006
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
[Current]
[General Information]
[Schedule]
[Arrangements]
Previous years:
[Autumn 2005]
[Spring 2005]
[Autumn 2004]
[Spring 2004]
[Autumn 2003]
[Spring 2003]
[Autumn 2002]
[Spring 2002]
[Autumn 2001]
[Spring 2001]
- [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.
Registration via
TOPI.
- Time, place: Mondays 4:30-7 p.m.,
seminar room TB353.
- Coordinator:
Pekka Orponen,
room TA348.
- Registration by
TOPI.
- Prerequisites: Basic knowledge of probability
theory, linear algebra and discrete mathematics.
- Assets: Familiarity with stochastic processes,
combinatorial optimisation,
computational complexity.
- 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
solution sets.
Week |
Date |
Topic (D&S section numbers refer to the
online edition) |
Session moderator |
Problems |
Slides |
4. | Jan 23 |
Opening, overview, handing out assigments
Random walks and electric networks (Doyle & Snell 1.1) |
Pekka Orponen |
1.1.2, 1.1.5, 1.1.6, 1.1.9 |
PDF |
5. | Jan 30 |
Random walks in two dimensions (Doyle & Snell 1.2) |
Leena Salmela |
1.2.2, 1.2.5, 1.2.6, 1.2.9 |
PDF |
6. | Feb 6 |
Random walks on finite networks (Doyle & Snell 1.3.1-1.3.4) |
André Schumacher |
1.3.3, 1.3.4, 1.3.8, 1.3.10 |
PDF |
7. | Feb 13 |
Thomson's principle and Rayleigh's monotonicity law
(Doyle & Snell 1.3.5, 1.4) |
Martti Meri |
1.3.11, 1.3.12, 1.4.10, 1.4.11 |
PDF |
8. | Feb 20 |
Random walks on infinite networks (Doyle & Snell 2.1-2.2) |
Pekka Orponen |
2.1.5, 2.1.6, 2.2.3, 2.2.5 |
PDF |
9. | Feb 27 |
No seminar. |
10. | Mar 6 |
The spectrum of a graph;
regular graphs and line graphs (Biggs 2-3) |
Alexey Kirichenko |
PDF |
PDF |
11. | Mar 13 |
Cycles and cuts;
spanning trees and associated structures (Biggs 4-5) |
Leena Salmela |
PDF |
PDF |
12. | Mar 20 |
The tree-number;
determinant expansions (Biggs 6-7) |
André Schumacher |
PDF |
PDF |
13. | Mar 27 |
Vertex-partitions and the spectrum (Biggs 8) |
Martti Meri |
PDF |
PDF |
14. | Apr 3 |
Laplacians and eigenvalues (Chung 1.1-1.4) |
Pekka Orponen |
PDF |
PDF |
15. | Apr 10 |
Eigenvalues and random walks (Chung 1.5) |
Alexey Kirichenko |
PDF |
PDF |
16. | Apr 17 |
Easter vacation: no seminar. |
- |
17. | Apr 24 |
The Cheeger constant and edge expansion (Chung 2.1-2.3) |
Satu Elisa Schaeffer |
- |
PDF |
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
problems.
- 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.
Core texts
- 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
here.)
- P. G. Doyle, J. L. Snell,
Random Walks and Electric Networks.
Mathematical Association of America, Washington DC, 1984.
(Online editions
here
and here.)
Auxiliary reading
- 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.
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 24 April 2006.
|