Graduate Theory Research Seminar (238901)
Fall semester 2007
Page under construction, last updated: 01.11.2007
previous update 09.10.2007
For inquiries please contact: J.A. Makowsky,
e-mail: janos@cs.technion.ac.il
Partition Functions and Graph Polynomials
For whom this seminar is meant?
For graduate students with a flair for
combinatorial mathematics and interdisciplinary questions.
Undergraduates may attend with special permission
of the lecturer.
The seminar is part of the
Graph Polynomial Project
.
Lecturer: Prof. J.A. Makowsky and participants
Time CHANGED: Monday, 16:30-18:30
Beginning: First Monday after the end of the STRIKE.
Student enquiries during the strike welcome.
Appointments by e-mail.
Place: Taub 601
Prerequisites:
Computability, some elementary graph theory,
some familiarity with linear and abstract algebra.
Format:
Two hours frontal presentations.
Requirements:
Edited version of frontal presentation or
final project.
Purpose of the seminar
The purpose of the seminar is twofold:
- Methodologically:
To introduce the participants into active research,
concentrating on creative reading skills, and the development
of research strategies in general.
- Thematically:
To practice reserach techniques with a particular topic
where many open but challenging questions abound.
Outline
Numeric graph invariants,
partition functions,
and graph polynomials
Partition functions arise physics.
They associate with a graph (signed graph)
a value in a commutative ring. The ring is mostly
a function ring over the reals or the reals themselves.
The partition functions are graph invariants.
Partition functons are intimately related to various
graph polynomials. Recently, Freedman, Lovasz and Schrijver
have given a very elegant characterization of graph invariants
which can be interpreted as partition functions.
In the seminar we shall take this characterization as a starting
point to explore further how graph polynomials
can be classified into interesting classes.
We shall use tools from combinatorics, logic and complexity theory.
No previous knowledge on graph polynomials is required!
Literature
-
N. Biggs, Interaction models,
London Mathematical Society Lecture Note Series, vol. 30, 1977
-
D. Welsh, Complexity: Knots, colourings and counting,
London Mathematical Society Lecture Note Series, vol. 186, 1993
-
Homepage of the Graph Polynomial Project
-
List of original papers as candidates for
presentation in the seminar.