Problems associated with the algorithmic counting of combinatorial structures arise naturally in many applications and also constitute an interesting sub-field of computational complexity theory. In this talk, we consider one of the most studied of such problems: that of counting proper colourings of bounded degree graphs. Here, a constant maximum degree $\Delta$ and a set of $q$ colours are fixed. The input is a graph $G$ of maximum degree at most $\Delta$, and a parameter $\varepsilon > 0$. The problem is to output “efficiently”, i.e. in time that grows polynomially in $1/\varepsilon$ and the size $n$ of the graph, and up to a multiplicative error of at most $(1+\varepsilon)$, the number of proper colourings of $G$ with the given set of $q$ colours.
The problem has been attacked using randomized Markov chain methods, and a delightfully simple analysis using the path coupling method gives an efficient randomized algorithm when $q \geq 2\Delta + 1$. The best currently known Markov chain analysis, due to Vigoda, requires $q \geq 11 \Delta / 6$. However, the condition required for efficient deterministic algorithms (i.e., those that do not use any randomness and do not have a probability of error) was until recently $q \geq 2.58 \Delta$, which lagged behind even the simple path coupling analysis. In this work, we improve this to $q \geq 2 \Delta$, thus finally matching at least the path coupling bound for deterministic algorithms. Our method, based on a paradigm proposed by Alexander Barvinok, uses information on the complex zeros of the associated Potts model partition function. Perhaps surprisingly, the information we need about the complex zeros of this partition function is obtained using methods inspired from previous analyses of phenomena related to Markov chain algorithms for the problem.
Part of the talk will also be a general survey of Barvinok’s paradigm and the growing body of work connecting it to more probabilistic notions.
Joint work with Singcheng Liu and Alistair Sinclair.