Advanced Topics in Computer Science (236603)

Spring semester 2011

Home page of the course: http://www.cs.technion.ac.il/~janos/COURSES/236603-11
last updated: 29.12.2010

Graph polynomials and graph invariants


In 2005-2006 I gave a similar course as a graduate seminar Graph polynomials and graph decompositions 238900 with Slides of seminar lectures.
See also lectures 10 and 11 of Logical Methods in Combinatorics 236605-09 given in the Winter Semester 2009/10.
For those students who have already taken 236603 before,
but on another topic, arrangements will be found to get credit again.

NEW: Projects: Topics and Assignments

UPDATED: Slides and abstracts of the lectures

Mailing List

Lecturer: Prof. J.A. Makowsky
Time: Sunday, 14:30-16:30.
Place: TBA


Prerequisites: The course is rather elementary.
Useful is some knowledge in elementary graph theory, computability and some familiarity with linear and abstract algebra.
Format: Two hours frontal presentations.
Requirements: Edited version of frontal presentation or final project.

Outline

A common generalization of counting problems are graph polynomials. The most prominent of these are the matching polynomials, the colouring polynomials and the Tutte polynomial. For general graphs these are often hard to compute (#P hard). There are also various multivariate generalizations of these polynomials.
The aim of the course is to study some of the more prominent graph polynomials such as and some more recently introduced graph polynomials, and to develop a general theory of graph polynomials.
Studying graph polynomials is a fascinating topic combining graph theory, combinatorics, algebra and complexity theory, and has applications beyond mathematics, in computer science, physics, chemistry and biology.

The course is part of a larger research project, the graph polynomial project, where we work on a Catalogoue of graph polynomials:

and is

suitable for students looking for MSc and PhD topics.

Literature