## T-79.7001 Postgraduate Course in Theoretical Computer Science (2–10 cr) P V## Spring 2006Spectral 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
## 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. |