Course manual 2023/2024

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.75 (75%) Tentamen
0.25 (25%) Huiswerk

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

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

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

Graph Polynomials and Algorithms