TCS / Studies / T-79.7001 Postgraduate Course in Theoretical Computer Science
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

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]


Current

  • [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.


General Information

  • 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.

Schedule

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. -

Arrangements

  • 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.

Seminar material (to be completed)

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.