Workshop

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

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: (See below for a growing list of abstracts)

Thursday 23 August all taks are in room D1.111

• 09.00 - 09.30 Coffee (Central hall Science Park 904)
• 09.30 - 09.40 Opening: Eric Opdam
• 09.40 - 10.30 Alexander Barvinok: The interpolation method and its challenges
• 10.30 - 11.00 Coffee (in front of D1.111)
• 11.00 - 11.50 Leslie Goldberg: Computational Complexity and the Independence Polynomial
• 11.50 - 12.20 Matthew Jenssen: On kissing numbers and spherical codes in high dimensions
• 12.30 - 14.00 Lunch (cafeteria central hall)
• 14.00 - 14.50 Han Peters: Zeros of the Ising partition function
• 14.50 - 15.20 Mark Jerrum: Perfect simulation of the Hard Disks Model by Partial Rejection Sampling
• 15.20 - 15.50 Coffee (in front of D1.111)
• 15.50 - 16.40 Martin Loebl: Binary Linear Codes via 4D Discrete Ihara-Selberg Function
• 16.40 - 17.10 Tyler Helmuth: Algorithmic Pirogov-Sinai Theory
• 17:30- Drinks and dinner at Polder (Science Park 201)

Friday 24 August all talks are in room D1.111

• 09.00 - 09.30 Coffee
• 09.30 - 10.20 Amin Coja-Oghlan: Spin systems on Bethe lattices
• 10.20 - 10.50 Heng Guo: A polynomial-time approximation algorithm for all-terminal network reliability
• 10.50 - 11.20 Coffee (in front of D1.111)
• 11.20 - 12.10 Péter Csikvári: Statistical matching theory
• 12.10 - 12.40 Ferencs Bencs: Christoffel--Darboux type identities for the independence polynomial
• 12.40 - 14.20 Lunch
• 14.20 - 14.50 Ewan Davies
• 14.50 - 15.40 Lex Schrijver: Partition functions, graph limits, and knot theory
• 15:40- Drink and bites (cafeteria central hall)

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:

• Alexander Barvinok (University of Michigan)

Title: The interpolation method and its challenges

Abstract: I'll describe a general approach which allows one to approximate the partition function in a complex domain, provided the function does not have zeros in a slightly larger domain. Among of the challenges of the method is that the proofs supply various thresholds of approximability and only rarely we know if the thresholds are optimal. For example, we know that the permanent of a complex matrix is well-approximable if the entries are within distance 0.5 from 1 and the permanent of a real positive 3-dimensional tensor is approximable if the entries are within a factor of sqrt{2} +1 of each other, but we don't know if these bounds are anywhere near the optimum.

• Amin Coja-Oghlan (Goethe University, Frankfurt am Main)

Title: Spin systems on Bethe lattices

Abstract: In an extremely influential paper Mezard and Parisi (2001) put forward an analytic but non-rigorous approach called the cavity method for studying spin systems on the Bethe lattice, i.e., the random $d$-regular graph. Their technique was based on certain hypotheses; most importantly, that the phase space decomposes into a number of Bethe states that are free from long-range correlations and whose marginals are given by a recurrence called Belief Propagation. I will show how we can establish this decomposition rigorously for a very general family of spin systems, and how the free energy can be computed from this decomposition. I’ll also present a variational formula for the free energy.

• Péter Csikvári (Eötvös Loránd, Budapest)

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.

• Leslie Ann Goldberg (University of Oxford)

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.

• Martin Loebl (Charles University, Prague)

Title: Binary Linear Codes via 4D Discrete Ihara-Selberg Function

Abstract: Weight enumerator of each binary linear code is expressed as a (formal) product. This generalises a result suggested by Feynman and proved by Sherman in the beginning of the 60's on the generating function of even edge-sets of planar graphs.

• Han Peters (University of Amsterdam)

Title: Zeros of the Ising partition function

Abstract: The Ising model originated in statistical physics, where it was used to model magnetic objects. Absence of zeros of the partition function implies the absence of phase transitions, i.e. it implies analytic dependence on the parameters, a classical result of Lee and Yang. More recently there has been considerable interest from the perspective of algorithmic complexity. In complexity theory, absence of zeros implies the existence of fast approximation algorithms.

The partition function of a graph depends on two parameters, a field-like parameter $\lambda$, and a temperature-like parameter $\beta$. A result of Lee-Yang from 1952 states that for the physically relevant $\beta \in [0,1]$, the partition function can only be zero when $\lambda$ lies on the unit circle. The famous Lee-Yang Theorem has received enormous attention in the literature. The exact $\lambda$-values for which the partition function is always non-zero has been studied, but not completely described. We will give a complete description for arbitrary graphs of maximal degree $d \ge 2$. Our result is obtained by reducing the problem to the setting of trees, where it can be studied using classical techniques from complex dynamical systems. (Joint work with Guus Regts)

• Lex Schrijver (University of Amsterdam and CWI Amsterdam)

Title: Partition functions, graph limits, and knot theory

Abstract: We give characterizations of partition functions and their relations to graph limits and knot theory.

Short talks will be given by:

• Heng Guo (University of Edinburgh)

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).

• Ewan Davies (University of Amsterdam)
• Matthew Jenssen (University of Oxford)

Title: On kissing numbers and spherical codes in high dimensions

Abstract: We prove a lower bound of $\Omega (d^{3/2}\cdot(2/\sqrt{3})^d)$ on the kissing number in dimension $d$. This improves the classical lower bound of Chabauty, Shannon, and Wyner by a linear factor in the dimension. We obtain a similar linear factor improvement to the best known lower bound on the maximal size of a spherical code of acute angle in high dimensions. Joint work with Felix Joos and Will Perkins.

• Mark Jerrum (Queen Mary, University of London)

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)

• Ferenc Bencs (Central European University, Budapest)

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.

• Tyler Helmuth

Title: Algorithmic Pirogov-Sinai Theory

Abstract: The cluster expansion and Pirogov-Sinai theory are techniques for understanding the perturbative regime of statistical mechanics models, i.e., at very high or very low temperatures. When applicable these techniques provide a great deal of information. I will explain how to combine these ideas with Barvinok’s method for approximate counting and sampling, and how this leads to efficient approximate counting and sampling algorithms for the Potts and hard-core models on finite subsets of Z^d. This is joint work with Guus Regts and Will Perkins.