Zeros of chromatic, flow and other polynomials

Workshop theme

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)

The application is closed

Timetable

Monday 21st January 2008
08:30 to 09:55	Registration	No Room Required
09:55 to 10:00	Welcome - David Wallace	Room 1
10:00 to 11:00	Alan Sokal Complex zeros of the chromatic and Tutte polynomials	Room 1
11:00 to 11:30	Coffee	No Room Required
11:30 to 12:30	David Jackson University of Waterloo Real zeros of chromatic and flow polynomials	Room 1
12:30 to 13:45	Lunch at Churchill College	No Room Required
14:00 to 15:00	Carsten Thomassen Technical University of Denmark Chromatic polynomials and a second Hamiltonian cycle	Room 1
15:00 to 15:30	Tea	No Room Required
15:30 to 16:00	Saeid Alikhani Universiti Putra Malaysia Chromatic roots and fibonacci numbers	Room 1
16:00 to 16:30	Kerri Morgan Monash University Chromatic factorisation of graphs	Room 1
16:30 to 17:30	Welcome Wine Reception	No Room Required
18:00 to 19:00	Dinner at Churchill College	No Room Required

Tuesday 22nd January 2008
10:00 to 11:00	Gordon Royle University of Western Australia Constructive resolution of two conjectures on real chromatic roots	Room 1
11:00 to 11:30	Coffee	No Room Required
11:30 to 12:00	Jason I Brown Dalhousie University On the zeros of independence and open set polynomials	Room 1
12:00 to 12:30	Klas Markström Umeå University Bounds for the numner of matchings in regular graphs	Room 1
12:30 to 13:45	Lunch at Churchill College	No Room Required
14:00 to 15:00	Fengming Dong Nanyang Technological University On graphs whose chromatic polynomials have no zeros in (1,2)	Room 1
15:00 to 15:30	Tea	No Room Required
15:30 to 16:00	Joab Winkler University of Sheffield New methods for solving high degree polynomial equations that have multiple roots	Room 1
16:00 to 16:30	William Faris University of Arizona The calculus of combinatorial constructions and Hopf algebras	Room 1
18:00 to 19:00	Dinner at Churchill College	No Room Required

Wednesday 23rd January 2008
10:00 to 11:00	Roberto Fernandez Université de Rouen Cluster expansions for hard-core systems: I introduction	Room 1
11:00 to 11:30	Coffee	No Room Required
11:30 to 12:30	Roberto Fernandez Université de Rouen Cluster expansions for hard-core systems: II convergence criteria	Room 1
12:30 to 13:45	Lunch at Churchill College	No Room Required
14:00 to 14:30	Milos Zahradnik Charles University, Prague A simple resummation method for cluster expansions	Room 1
14:30 to 15:00	David Wagner University of Waterloo Enumeration of spanning subgraphs with degree constraints	Room 1
15:00 to 15:30	Tea	No Room Required
15:30 to 16:00	Olga Holtz Technische Universität Berlin On polynomials arising from zonotopal algebra	Room 1
16:00 to 16:30	Irasema Sarmiento Università degli Studi di Roma Tor Vergata The topological Tutte polynomials of Bollobas and Riordan: properties and relations to other graph polynomials	Room 1
16:30 to 17:30	Julius Borcea Stockholm University Geometry of polynomials and applications	Room 1
18:00 to 19:00	Dinner at Churchill College	No Room Required

Thursday 24th January 2008
10:00 to 11:00	Alexander Scott University of Oxford Independent sets, lattice gases and the Loavsz Local Lemma	Room 1
11:00 to 11:30	Coffee	No Room Required
11:30 to 12:00	Svante Janson Uppsala Universitet Zeros of truncated binomial polynomials	Room 1
12:30 to 13:45	Lunch at Churchill College	No Room Required
14:00 to 15:00	Robert Shrock State University of New York Zeros of chromatic and Tutte (Potts) polynomials and general Ising model, and their accumulation sets for families of graphs	Room 1
15:00 to 15:30	Tea	No Room Required
15:30 to 16:00	Shu-Chiuan Chang National Cheng Kung University Zeros of graph-counting polynomials and their accumulation sets	Room 1
16:00 to 16:30	Halina Bielak Maria Curie-Sklodowska University Chromatic zeros for some recursively defined families of graphs	Room 1
16:30 to 17:00	Joseph Slawny Virginia Polytechnic Institute and State University Self-dual spin systems, zeros of partition function, and error correcting codes	Room 1
19:30 to 23:00	Conference Dinner at Emmanuel College	No Room Required

Friday 25th January 2008
10:00 to 11:00	Norman Biggs London School of Economics Complex roots of chromatic polynomials	Room 1
11:00 to 11:30	Coffee	No Room Required
11:30 to 12:30	Jesper Jacobsen Université Paris Saclay Representations and partition function zeros of the Potts model with and without boundaries	Room 1
12:30 to 13:45	Lunch at Churchill College	No Room Required
14:00 to 14:30	Christian Tanguy Dominant traits in the zeros of two-variate two-terminal reliability polynomials	Room 1
14:30 to 15:00	Chris Smyth University of Edinburgh Integer symmetric matrices with spectral radius at most 2.019	Room 1
15:00 to 15:30	Tea	No Room Required
15:30 to 16:30	Problem session	Room 1
18:00 to 19:00	Dinner at Churchill College	No Room Required

Speakers

Saeid Alikhani Universiti Putra Malaysia
Halina Bielak Maria Curie-Sklodowska University
Norman Biggs London School of Economics
Julius Borcea Stockholm University
Jason I Brown Dalhousie University
Shu-Chiuan Chang National Cheng Kung University
Fengming Dong Nanyang Technological University
William Faris University of Arizona
Roberto Fernandez Université de Rouen
Olga Holtz Technische Universität Berlin
David Jackson University of Waterloo
Jesper Jacobsen Université Paris Saclay
Svante Janson Uppsala Universitet
Klas Markström Umeå University
Kerri Morgan Monash University
Gordon Royle University of Western Australia
Irasema Sarmiento Università degli Studi di Roma Tor Vergata
Alexander Scott University of Oxford
Robert Shrock State University of New York
Joseph Slawny Virginia Polytechnic Institute and State University
Chris Smyth University of Edinburgh
Alan Sokal
Christian Tanguy
Carsten Thomassen Technical University of Denmark
David Wagner University of Waterloo
Joab Winkler University of Sheffield
Milos Zahradnik Charles University, Prague

Show All