Advanced Combinatorics: Zeros of Graph Polynomials, Markov Chains and Algorithms

6 EC

Semester 1, period 1, 2

5334ACZG6Y

Owner Master Mathematics
Coordinator dr. Guus Regts
Part of Master Mathematical Physics, Master Mathematics, Master Mathematics, specialization Algebra and Geometry, year 1Master Mathematics, specialization Mathematical Physics, year 1

Course manual 2019/2020

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 three algorithmic approaches for approximate computations: one through rapid mixing of Markov Chains, one based on decay correlation decay 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

  • Counting, Sampling and Integrating: Algorithms and Complexity, by Mark Jerrum

  • Lecture notes and research papers to be determined later.

Objectives

  • To learn how to read mathematics books and papers at a research level
  • Learn how knowledge of zeros of partition functions is related to the design of algorithms
  • Learn techniques for proving absence (or existence) of zeros for graph polynomials in certain domains
  • Learn Markov chain techniques for computing evaluations of graph polynomials
  • Learn correlation decay techniques for computing evaluations of graph polynomials

Teaching methods

  • Lecture

Learning activities

Activity

Hours

Hoorcollege

28

Tentamen

3

Self study

137

Total

168

(6 EC x 28 uur)

Attendance

The programme does not have requirements concerning attendance (OER-B).

Assessment

Item and weight Details

Final grade

0.75 (75%)

Tentamen

0.25 (25%)

Project

The project will be a combination of homework and or student presentation.

Assignments

25 % of the final mark will be based on a combination of Homework problems and or presentations given by students.

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 Introduction to the course. The independence polynomial  
2 The Tutte polynomial and some of its properties  
3 Counting perfect matchings in planar graphs and the matrix tree theorem  
4 Counting vs. Sampling  
5 Sampling approach for counting colorings  
6 Counting matchings 1: Sampling (optional)  
7 Counting matchings 2: Correlation decay  
8 The Interpolation method 1: Independence polynomial  
9

The Interpolation method 2: the permanent

 

  
10 The Interpolation method 3: the Tutte polynomial  
11 Students presentations/ research papers  
12 Students presentations/ research papers  
13 Students presentations/ research papers  
14 Students presentations/ research papers  
15 Students presentations/ research papers  
16    

Timetable

The schedule for this course is published on DataNose.

Contact information

Coordinator

  • dr. Guus Regts

Staff

  • dr. V.S. Patel