Graph Polynomials and Algorithms

6 EC

Semester 1, period 1, 2

5334GRPA6Y

Owner Master Mathematics
Coordinator dr. Guus Regts
Part of Master Mathematics, specialization Algebra and Geometry, year 1Master Mathematics, specialization Analysis and Dynamical Systems, year 1Master Mathematics, specialization Stochastics , year 1Master Mathematics, specialisation Discrete Mathematics and Quantum Information, year 1

Course manual 2025/2026

Course content

Graph polynomials and partition functions play an important role in statistical physics and combinatorics. In this course we will introduce several of them such as the independence polynomial, the Tutte polynomial, the matching polynomial and several others. The main focus of the course will be on algorithmic techniques for (approximately) computing evaluations of these polynomials. We consider exact algorithms, based on determinants, for the dimer problem on planar graphs and for enumerating spanning trees. We consider two algorithmic approaches for approximate computations: one through rapid mixing of Markov Chains, and one more recent approach based on the locations of the complex roots of the polynomial.

Study materials

Literature

    • Combinatorics and  Complexity of Partition functions, by Alexander Barvinok (see here (Links to an external site.) for a pdf) and
    • Counting Sampling and Integrating: Algorithms and Complexity, by Mark Jerrum. 

Syllabus

  • Lecture notes Graph Polynomials and Algorithms, available via Canvas

Objectives

  • Learn how knowledge of zeros of partition functions/ rapidly mixing Markov chains is related to the design of algorithms.
  • Learn techniques for proving absence (or existence) of zeros for graph polynomials in certain domains.
  • Learn techniques for proving rapid mixing of Markov chains.
  • Learn basic algebraic and combinatorial properties of graph polynomials such as the Tutte polynomial and the independence polynomial.

Teaching methods

  • Lecture
  • Self-study

Learning activities

Activity

Hours

Hoorcollege

28

Tentamen

3

Self study

137

Total

168

(6 EC x 28 uur)

Attendance

This programme does not have requirements concerning attendance (TER-B).

Assessment

Item and weight Details

Final grade

0.7 (70%)

Tentamen

0.3 (30%)

Midterm

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

WeeknummerOnderwerpenStudiestof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Contact information

Coordinator

  • dr. Guus Regts