Combinatorics, Probability and Statistical Mechanics

Programme

Thursday 10 May 2007

All talks will be in Lecture Room B1.01 in the Mathematics Institute

13:00 – 14:00 LeslieAnn Goldberg (Liverpool)
Matrix Norms and Rapid Mixing for Spin Systems

14:00 – 15:00 Martin Loebl (Prague)
Jones polynomials, q-counting, and quantum computing

16:00 – 17:00 Roberto Fernández (Rouen)
Partitionability of graphs and the convergence of cluster expansions

Abstracts

LeslieAnn Goldberg:
We give a systematic development of the application of matrix norms to rapid mixing in spin systems. We show that rapid mixing of both random update Glauber dynamics and systematic scan Glauber dynamics occurs if any matrix norm of the associated dependency matrix is less than 1. The analysis can be improved for the case in which the diagonal of the dependency matrix is 0 (as in heat bath dynamics). We apply the matrix norm methods to random update and systematic scan Glauber dynamics for colouring various classes of graphs.

Martin Loebl:
I will present an overview of the results on calculations of Jones polynomial obtained partly with Stavros Garoufalidis. An example: given a generic planar projection of a link with n crossings, we define 10n \times 10n matrix whose permanent equals to the Jones polynomial. This result accompanied with recent work of Freedman, Kitaev, Larson and Wang provides a Monte-Carlo algorithm to any decision problem belonging to the class BQP, i.e., such that it can be computed with bounded error, using quantum resources, in polynomial time.

Roberto Fernández:
We present an alternative approach for the sum of cluster expansions that results in improved convergence conditions. The approach is based on a more detailed use of partitionability schemes of the connected spanning subgraphs of the incompatibility graph. The resulting majorizing series is then shown to converge through an iterative procedure that incorporates conditions of the type proposed by Kotecky-Preiss and Dobrushin. This strategy leads to improvements in the presence of triangle diagrams; in particular it produces the exact radius of convergence for complete graphs. Recent applications of this approach include better determinations of the region free of zeros of chromatic polynomials, and of the uniqueness regions for systems of hard spheres.

For further information contact Roman Kotecky.