2-day Workshop on Algorithmic and Combinatorial Aspects of Partition Functions

Organizers: Viresh Patel and Guus Regts

Dates: August 23 and 24.

Location: Science Park 904 Amsterdam (see map).

Topic: The study of various types of partition functions is a very active area of research and lies at the interface of combinatorics, probability, theoretical computer science, and statistical physics. The partition function of the Potts model and the hardcore model, also known as the Tutte polynomial and the independence polynomial respectively are prototypical examples. Some of the fundamental questions in this area include: What sort of network structure allows for efficient computation of the partition function? Which network structures maximizes/minimizes the partition function? How does the partition function of a random network behave? Recent developments have shown strong connections between phase transitions in statistical physics and answers to these type of questions. The aim of the workshop is to bring together researchers working on different aspects of partition functions in order to exchange ideas and learn about new developments.

Invited Speakers: Alexander Barvinok (University of Michigan), Amin Coja-Oghlan (Goethe University, Frankfurt am Main), Péter Csikvári (Eötvös Loránd, Budapest), Leslie Ann Goldberg (University of Oxford) , Martin Loebl (Charles University, Prague), Han Peters (University of Amsterdam) and Lex Schrijver (University of Amsterdam and CWI Amsterdam).

Participation: Participation and the conference dinner are free of charge, but participants should register and this can be done by clicking on this link.

Program: The program consists of talks by the invited speakers and contributed talks (20 min). Below there is a list of all speakers (sometimes) with titles and abstract. More details will be added later. Please send an email before the 1st of July, providing a short abstract if you wish to give a contributed talk. There are limited funds available for participant support.

Support: We gratefully acknowledge funding from Networks and NWO.

Local information: The workshop takes place in the beautiful city of Amsterdam. Sciencepark 904 can be reached by busses 40 and 240 from Amstel station (see this website for directions) and by a direct train connection from the central station (see this website for timetables).

Titles and Abstracts.

Invited Speakers:

Title: Statistical matching theory

Abstract: In this talk I survey some recent developments on statistical properties of matchings of very large and infinite graphs. I will discuss extremal graph theoretic results like Schrijver's theorem on the number of perfect matchings of regular bipartite graphs and its variants from the point of view of graph limit theory. I will also give some results about the the number of matchings of finite and infinite vertex-transitive graphs.

Title: Computational Complexity and the Independence Polynomial

Abstract: The independence polynomial is one of the most well-studied graph polynomials, arising in combinatorics and computer science. It is also known in statistical physics as the partition function of the "hard-core model''. After describing the polynomial, I will tell you something about the complexity of approximating this polynomial, including the now-classical breakthrough results of Weitz and Sly, incursions into the complex plane by Harvey, Srivastava, and Vondrak and by Patel and Regts and finally more recent work using tools from complex analysis by Peters and Regts and also in joint work with Bezakova, Galanis, and Stefankovic.

Short talks will be given by:

Title: A polynomial-time approximation algorithm for all-terminal network reliability

Abstract: All-terminal network reliability is the probability that, in a undirected graph, assuming each edge fails independently, the remaining graph is still connected. We will present a fully polynomial-time randomised approximation scheme (FPRAS) for this problem. Our main contribution is to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in bi-directed graphs is bounded by a polynomial in the size of the input. Joint work with Mark Jerrum (QMUL).

Title: Perfect simulation of the Hard Disks Model by Partial Rejection Sampling

Abstract: I'll present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in $O(\log n)$ rounds, where $n$ is the expected number of disks. The method extends easily to the hard spheres model in $d>2$ dimensions. If time permits, I'll describe an alternative perspective of the partial rejection sampling method that seems better adapted to proving correctness and analysing run-time in the continuous state space setting, Joint work with Heng Guo (Edinburgh)

Title: Christoffel--Darboux type identities for the independence polynomial

Abstract: In this talk I will introduce certain identities for independence polynomials, that are similar to the Christoffel--Darboux identities used in the theory of orthogonal polynomials. As an application, we will see that some conditions on the induced subgraphs of a graph $G$ translates to results on zero-free regions of the independence polynomial of $G$. In particular we give a new proof of a theorem of Chudnovsky and Seymour, which states that the independence polynomial of a claw-free graph has only real zeros.