Zeros of Graph Polynomials

21 January to 25 January 2008

Isaac Newton Institute for Mathematical Sciences, Cambridge, UK

Organisers: Professor Bill Jackson (Queen Mary, London) and Professor Alan Sokal (NYU and UCL)

in association with the Newton Institute programme Combinatorics and Statistical Mechanics (14 January to 4 July 2008)

Programme | Participants | Application | Accommodation and Cost | Accepted Contributed Talks | Accepted Posters | Web Seminars

Theme of Workshop:

The workshop will study the zero distribution of polynomials canonically associated to graphs. Examples include the chromatic polynomial, the reliability polynomial, the Tutte polynomial, the independent-set polynomial and the matching polynomial. From the point of view of statistical physics, these polynomials are nothing other than the partition functions of standard statistical-mechanical models (e.g. the Ising model, the Potts model, the lattice gas, the monomer-dimer model) living on the graph. Combinatorialists study the real and complex zeros of such polynomials to ascertain how they are related to the combinatorial properties of the underlying graph (planarity, chromatic number, maximum degree, connectivity, etc.). The questions being investigated thus arise naturally from combinatorics; but key elements of the intuition needed for their solution typically come from statistical physics, in particular from the theory of phase transitions and critical phenomena.

The workshop will bring together some of the principal researchers in this field to review recent advances and to brainstorm concerning the many unsolved problems. It will also feature tutorial seminars describing the main results and proof techniques, such as deletion/contraction, the multivariate approach, cluster expansion, and transfer matrices. The topics will be of interest to combinatorial mathematicians, mathematical physicists, theoretical physicists and computer scientists.

Keynote Speakers:

Norman Biggs (LSE), Christian Borgs (Microsoft Research, Seattle), Fengming Dong (Singapore), Roberto Fernandez (Rouen), Bill Jackson (Queen Mary, London), Jesper Jacobsen (Paris-Sud), Gordon Royle (Western Australia), Robert Shrock (SUNY-Stony Brook), Alex Scott (Oxford), Alan Sokal (NYU and UCL), Carsten Thomassen (Technical University of Denmark).

Local Information | Newton Institute Map | Combinatorics and Statistical Mechanics | Workshops | Newton Institute Home Page