Workshop Partition functions: zeros, unstable dynamics and complexity

Preliminary schedule

• 10:00-10:25 Welcome with coffee and tea

• 10:25-10:30 Opening

• 10:30-11:30 Andreas Galanis: Metastability for the ferromagnetic Potts model

The Potts model on a graph G is the generalisation of the Ising model to q>2 spins, whose configurations consist of all possible q-spin assignments to the vertices of the graph G.The model is further parameterised by a parameter β which controls the weight of a spin-assignment. We will focus on the ferromagnetic case where β>0 and neighboring spins are favored to be the same in the underlying distribution.

Unlike the antiferromagnetic case, the ferromagnetic model is believed to exhibit certain metastability phenomena as the parameter β changes, which make the analysis of standard algorithms for counting/sampling even more challenging, including for example algorithms based on Markov chains, or the interpolation method.In this talk, we will review recent developments on how to detail these metastability phenomena on the class of random regular graphs and how they connect to algorithms and complexity. Based on joint work with A. Coja-Oghlan, L.A. Goldberg, J.B. Ravelomanana, D. Stefankovic, and E. Vigoda.

• 11:30-12:00 Coffee break

• 12:00-12:30 Jeroen Huijben: Approximating the chromatic polynomial is as hard as computing it exactly

In this talk we will look at the computational problem of approximating the chromatic polynomial Z(G;q) for non-real, algebraic numbers q. There are many results about approximating the more general Tutte polynomial, but this case was still open. We will reduce exact computation of the chromatic polynomial to approximating it, and thus show this problem is #P-hard. Many steps are quite general and can be applied to other graph polynomials. The difficulty for the chromatic polynomial is constructing enough series-parallel graphs to use as gadgets. Based on joint work with Ferenc Bencs and Guus Regts.

• 12:30-13:00 Ferenc Bencs: Convergence of the free-energy of d-regular graphs

Abstract: Let (G_n) be a locally convergent sequence of d-regular graphs (for example: n\times n torus grid, random d-regular graphs, etc.). In general is it true that the free-energy of spin-models per site is convergent along this convergence? We will introduce a subgraph counting polynomial of graphs and with its help we will show that the answer is yes if the interaction matrix of the spin-model has rank 2. It is a joint work with Márton Borbényi and Péter Csikvári.

• 13:00-14:30 Lunch at Polder

• 14:30-15:00 David de Boer: Random colourings of trees with constant down degree

Denote (T^n_d, r) for the rooted tree with root r, where each vertex has d children and the leaves are at distance exactly n from r. Fix a colouring with q coloursof the leaves, and look at a random proper colouring of T^n_d that agrees with the colours we fixed on the leaves. What is the probability that the root gets colour 1 under such a proper colouring? Is it 1/q, or does it depend on the fixed colouring of the leaves? If we let the distance between the root and the leaves grow, will this tend to 1/q? After looking at this as a warm up, we will allow non proper colourings and discuss results in this setting. This talk is based on joint work with Ferenc Bencs, Pjotr Buys and Guus Regts.

• 15:00-16:00 Alexander Barvinok: Computing theta function

Let f: R^n —> R be a positive definite quadratic form and let y be a point in R^n. We present a fully polynomial randomized approximation scheme (FPRAS) for computing the sum of exp{-f(x)} over the integer points x, provided the eigenvalues of f lie in the interval roughly between s and e^s, and for computing the sum exp{-f(x-y)} over the integer points x, provided the eigenvalues of f lie roughly between e^{-s} and 1/s for some s > 3. To compute the first sum, we represent it as the integral of some explicit log-concave function on R^n and to compute the second sum, we use the reciprocity relation for theta functions. The polynomial interpolation method plays a role too: although so far it cannot match the bounds obtained via the Markov Chain Monte Carlo integration of log-concave functions, it does allow one to compute the sums in some situations that do not reduce to the integration of log-concave functions.

• 16:00-17:00 Drinks at Polder.