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:

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