Zeros of Chromatic, Flow and Other Polynomials
Monday 21st January 2008 to Friday 25th January 2008
08:30 to 09:55  Registration  
09:55 to 10:00  Welcome  David Wallace  INI 1  
10:00 to 11:00 
Complex zeros of the chromatic and Tutte polynomials In this introductory talk, I begin by showing how the chromatic and flow polynomials are special cases of the multivariate Tutte polynomial, and I sketch why it is often advantageous to "think multivariate", even when one is ultimately interested in a univariate specialization. I then explain briefly why the complex zeros of these polynomials are of interest to statistical physicists in connection with the LeeYang picture of phase transitions. Finally, I summarize what is known  and above all, what is _not_ known  about the complex zeros of these polynomials. A general reference for this talk is: arXiv:math/0503607 [math.CO] Alan D. Sokal The multivariate Tutte polynomial (alias Potts model) for graphs and matroids More details on various aspects can be found in: arXiv:math/0301199 [math.CO] Gordon Royle, Alan D. Sokal The BrownColbourn conjecture on zeros of reliability polynomials is false arXiv:math/0202034 [math.CO] YoungBin Choe, James G. Oxley, Alan D. Sokal, David G. Wagner Homogeneous multivariate polynomials with the halfplane property arXiv:condmat/0012369 [condmat.statmech] Alan D. Sokal Chromatic roots are dense in the whole complex plane arXiv:condmat/9904146 [condmat.statmech] Alan D. Sokal Bounds on the Complex Zeros of (Di)Chromatic Polynomials and PottsModel Partition Functions 
INI 1  
11:00 to 11:30  Coffee  
11:30 to 12:30 
Real zeros of chromatic and flow polynomials I will survey proof techniques, results, and open problems concerning the real zeros of chromatic polynomials and flow polynomials of graphs. In particular I will present a multivariate proof, due to Alan Sokal and myself, of the result that chromatic polynomials have no roots in the interval (1,32/27], which is much simpler than my original proof. A general, but dated, reference for this talk is: Bill Jackson, Zeros of Chromatic and Flow Polynomials of Graphs, arXiv:math/0205047v2 [math.CO] 
INI 1  
12:30 to 13:45  Lunch at Churchill College  
14:00 to 15:00 
Chromatic polynomials and a second Hamiltonian cycle The chromatic polynomial was introduced by Birkhoff in 1912 in order to study the 4Color Problem. Although the chromatic polynomial has not been very successful for solving coloring problems, it has served as inspiration for other problems in graph theory. In this talk, we describe some graph problems and resuls related to the roots of a chromatic polynomial, in particular the search for a second Hamiltonian cycle. Also a possible listchromatic polynomial will be discussed. 
INI 1  
15:00 to 15:30  Tea  
15:30 to 16:00 
Chromatic roots and fibonacci numbers We prove that all natural power of golden ratio, cannot be a root of any chromatic polynomial. We also consider generalized Fibonacci sequences and prove that all 2nanacci constants and all natural powers of them cannot be root of any chromatic polynomial. Finally, we introduce new numbers related to nannaci numbers and ask a question similar to Beraha question. 
INI 1  
16:00 to 16:30 
K Morgan ([Monash]) Chromatic factorisation of graphs We consider factorisation of the chromatic polynomial as a first step in an algebraic study of the roots of this polynomial. The chromatic polynomial of a graph is said to have a chromatic factorisation if P(G,?)= P(H1,?)P(H2,?)/P(Kr ,?) for some graphs H1 and H2 and clique Kr . It is known that the chromatic polynomial of any cliqueseparable graph, that is, a graph containing a separating rclique, has a chromatic factorisation. We show that there exist other chromatic polynomials that have chromatic factorisations but are not the chromatic polynomial of any cliqueseparable graph and identify all such chromatic polynomials of degree at most 10. We introduce the notion of a certificate of factorisation, which provides an explanation for such a factorisations, and find certificates for all cases of degree ? 9. These certificates are much shorter than the upper bound of O(n 22n/2). Furthermore, we construct an infinite family of noncliqueseparable graphs that have chromatic factorisations and give certificates of factorisation for graphs belonging to this family. 
INI 1  
16:30 to 17:30  Welcome Wine Reception  
18:00 to 19:00  Dinner at Churchill College 
10:00 to 11:00 
Constructive resolution of two conjectures on real chromatic roots In this talk I will discuss the recent resolution of two conjectures on the real roots of the chromatic polynomial of a graph, both of which were resolved by the construction of suitable families of graphs. The first of these is Bill Jackson’s conjecture that 3connected nonbipartite graphs do not have chromatic roots in the interval (1,2), which turns out to be false. The counterexamples to this conjecture all have an intriguing connectivity property that seems unavoidable, lending support to a recent conjecture of Dong & Koh concerning graphs with no chromatic roots in (1,2). The second conjecture that I discuss is Sami Beraha’s conjecture that there are planar graphs with real chromatic roots arbitrarily close to the point x = 4. For many years, the largest known real planar chromatic root was 3.8267 ...from a graph found by Douglas Woodall that appeared to have no obvious structure. However it turns out that viewed in the right way, this graph is the first member of an infinite sequence of graphs with real chromatic roots converging to 4. The most wanted conjecture in the study of real chromatic roots is Birkhoff & Lewis’s conjecture that [4,5) is a rootfree interval for planar graphs, but unfortunately the resolution of Beraha’s conjecture appears to give no traction whatsoever on this conjecture. 
INI 1  
11:00 to 11:30  Coffee  
11:30 to 12:00 
On the zeros of independence and open set polynomials While the zeros of chromatic and flow polynomials have attracted much attention in the research literature, there are some other lesser known polynomials on discrete structures whose zeros are also worthy of investigation. Independence polynomials arise as generating functions of the number of independent sets of each cardinality in a graph. Open set polynomials enumerate open sets in a finite topology. We survey what is known about the nature and location of the zeros, with results ranging from bounds on the moduli to density and realness of the zeros, and even including a fractal or two thrown in for good measure. 
INI 1  
12:00 to 12:30 
Bounds for the numner of matchings in regular graphs In this talk I will first present a group of conjectures on the number of kedge matchings in a regular graph on n vertices. Next I will present the partial results obtained so far. In order to get lower bounds for the number of matchings for all densities k/n we make use of the fact that the matching polynomial of a graph has real zeros. 
INI 1  
12:30 to 13:45  Lunch at Churchill College  
14:00 to 15:00 
FM Dong ([Nanyang Technological]) On graphs whose chromatic polynomials have no zeros in (1,2) The study of zero distribution of chromatic polynomials has attracted the attention of researchers working in both Mathematics and Physics. In this talk, I shall focus on the study of graphs which have no chromatic zeros in (1, 2). One of the motivations of this study is to find some useful methods to attack the famous conjecture that every plane graph has no chromatic zeros in (4, 5). Due to Jackson’s and Thomassen’s results, it is now confirmed that there are only three maximal intervals (?, 0), (0, 1) and (1, 32/27], in which all chromatic polynomials are zerofree. Jackson conjectured in 1993 that every 3connected nonbipartite graph has no chromatic zeros in (1, 2). It was recently disproved by Royle’s discovery of some counterexamples. However, Jackson’s conjecture triggered the study of graphs which have no chromatic zeros in (1, 2). Let F be the family of K2 and 2connected graphs which have no chromatic zeros in (1, 2). We can show that this family is ‘closed’ in some senses under certain operations. Applying this result, we are able to find some subfamilies of graphs which have no chromatic zeros in (1, 2). A connected graph G is said to be ?tough if the number of components of G  S is at most Sfor all nonempty independent sets S in G. We observed that, up to now, all 2connected graphs in F that have been discovered are ?tough. Based on this observation, we conjectured that every ?tough graph belongs to F. The condition for this conjecture is weaker than that in Thomassen’s conjecture: every Hamiltonian graph contains no chromatic zeros in (1, 2). Finally we shall consider non?tough graphs that do have chromatic zeros in (1, 2). 
INI 1  
15:00 to 15:30  Tea  
15:30 to 16:00 
New methods for solving high degree polynomial equations that have multiple roots The determination of the roots of a polynomial is a classical problem in mathematics to which much effort has been devoted. There exist many methods for their computation, but they all fail on high degree polynomials, or polynomials that have multiple roots. In particular, roundoff errors due to finite precision arithmetic are sufficient to cause a multiple root to break up into a cluster of simple roots, and the problems are compounded when the coefficients of the polynomial are subject to error. In this talk, I will describe a radically new, and significantly better, method of computing the roots of a polynomial. The method has two stages: Stage 1: Perform a succession of greatest common divisor (GCD) computations to calculate the multiplicity of each distinct root. Stage 2: Use the information from Stage 1 to calculate the roots, and then refine them using the method of nonlinear least squares. The GCD calculations in Stage 1 use structured matrix methods, algebraic geometry, the least squares equality problem and methods of information theory. The nonlinear least squares in Stage 2 is performed by the GaussNewton iteration. Examples will be given to illustrate the success of the method. 
INI 1  
16:00 to 16:30 
The calculus of combinatorial constructions and Hopf algebras Bergeron, Labelle, and Leroux describe in their book a calculus of combinatorial constructions. This systemizes many of the constructions that lead to exponential generating functions. Many of the ideas are related to Hopf algebra notions; the talk will explore these connections. 
INI 1  
18:00 to 19:00  Dinner at Churchill College 
10:00 to 11:00 
R Fernandez ([Rouen]) Cluster expansions for hardcore systems: I introduction CLUSTER EXPANSIONS FOR HARDCORE SYSTEMS: I INTRODUCTION The talk will be an introductory presentation of cluster expansions for models with self and nearestneighbour exclusions. It will focus on the following questions: what are cluster expansions?, what type of information they yield?, how are they used? The general abstract framework polymer models will be introduced, illustrated with a number of classical examples. CLUSTER EXPANSIONS FOR HARDCORE SYSTEMS: II CONVERGENCE CRITERIA The successive convergence criteria proposed for cluster expansions will be presented and compared. The talk will include a discussion of the contrasting conceptual approaches of the different proofs, as well as numerical consequences for benchmark examples. If time permits, an alternative probabilistic scheme will also be reviewed. This scheme, which is not based on expansions, yields weaker results but does not make use of expansion methods and leads to a perfect simulation algorithm. 
INI 1  
11:00 to 11:30  Coffee  
11:30 to 12:30 
R Fernandez ([Rouen]) Cluster expansions for hardcore systems: II convergence criteria CLUSTER EXPANSIONS FOR HARDCORE SYSTEMS: I INTRODUCTION The talk will be an introductory presentation of cluster expansions for models with self and nearestneighbor exclusions. It will focus on the following questions: what are cluster expansions?, what type of information they yield?, how are they used? The general abstract framework polymer models will be introduced, illustrated with a number of classical examples. CLUSTER EXPANSIONS FOR HARDCORE SYSTEMS: II CONVERGENCE CRITERIA The successive convergence criteria proposed for cluster expansions will be presented and compared. The talk will include a discussion of the contrasting conceptual approaches of the different proofs, as well as numerical consequences for benchmark examples. If time permits, an alternative probabilistic scheme will also be reviewed. This scheme, which is not based on expansions, yields weaker results but does not make use of expansion methods and leads to a perfect simulation algorithm. 
INI 1  
12:30 to 13:45  Lunch at Churchill College  
14:00 to 14:30 
A simple resummation method for cluster expansions I will present a simple and (possibly) new method of organizing the (+/ cancellations in the) cluster expansions of polymer models, hard repulsion case. The method is suitable for models where polymers are "cycles" or closed paths in a lattice (KramersWannier representation of the Ising model, perturbations of massless Gaussians) also in several cases where expansions are only nonabsolutely summable. 
INI 1  
14:30 to 15:00 
Enumeration of spanning subgraphs with degree constraints For a finite (multi) graph G=(V,E) and functions f,g: V > N and natural number j, consider the number of (f,g)factors of G with exactly j edges. We investigate logarithmic concavity properties of such sequences (as j varies with f and g fixed) by considering the location of zeros of their generating functions. The case f==0 and g==1 is that of the HeilmannLieb theorem on matching polynomials. The more general case f<=g<=f+1 appears in earlier work of mine, and the case f==0 and g==2 was considered by Ruelle. We provide a unified approach to these cases via the halfplane property and the GraceWalshSzego coincidence theorem. As a byproduct we find a "circle theorem'' for the zeros of a weighted generating function for the set of all spanning subgraphs of G. 
INI 1  
15:00 to 15:30  Tea  
15:30 to 16:00 
On polynomials arising from zonotopal algebra Given a graph G, we consider its associated (linear) matroid X, and associate X with three kinds of algebraic structures called external, central, and internal. Each algebraic structure is given in terms of a pair of homogeneous polynomial ideals in n variables that are dual to each other. Algebraically, one encodes properties of the (generic) hyperplane arrangement H(X) associated to X, while the other encodes by duality the properties of the zonotope Z(X) built from the matrix X. These algebraic structures are then applied to obtain various statistics for the graph G. In particular, the Hilbert series of each of the three ideals turn out to be ultimately related to the Tutte polynomial of G, and the grading of the ideals turns out to be related to specific counting functions on subforests or on spanning trees of G. This leads to other combinatorial connections and several open problems as well. Related Links

INI 1  
16:00 to 16:30 
I Sarmiento ([Roma Tor Vergata]) The topological Tutte polynomials of Bollobas and Riordan: properties and relations to other graph polynomials In [BR01], [BR02], Bollob´as and Riordan defined analogs of the Tutte polynomial for graphs embedded in surfaces, thus encoding topological information lost in the classical Tutte polynomial. We pro vide a recipe theorem for these polynomials and use it to relate them to the generalized transition polynomial, the topological Tutte poly nomials defined in [Las75], [Las78], [Las79], the parametrized Tutte polynomial of [Zas92] and [BR99], and Bouchets TutteMartin poly nomial of isotropic systems. Various evaluations of these polynomi als of Bollob´as and Riordan, as well as insight into the topological information they encode. The relationship between the generalized transition polynomial and the topological Tutte polynomial extends a result of [Jae90] from planar graphs to arbitrary graphs by giving a relationship between the transition and the R polynomials. We also visit the Kauffman bracket in light of these relationships and that es tablished between it and the topolofical Tutte polynomial in [CP]. 
INI 1  
16:30 to 17:30 
Geometry of polynomials and applications We discuss closely related geometric properties of zero sets of multivariate polynomials such as real stability, the halfplane property, (Gårding) hyperbolicity and the strong Rayleigh property. In particular, using the latter we define a class of probability measures (called strongly Rayleigh) that contains uniform random spanning tree measures, determinantal measures (for contractions) and distributions for symmetric exclusion processes. We develop a theory of negative dependence for this class of measures and settle several conjectures of Liggett, Pemantle and Wagner. Examples and applications include extensions of Lyons' recent results on determinantal measures and the halfplane property for certain matroids studied by Sokal, Wagner et al. This is joint work with Petter Brändén (KTH) and Thomas M. Liggett (UCLA). Related Links

INI 1  
18:00 to 19:00  Dinner at Churchill College 
10:00 to 11:00 
Independent sets, lattice gases and the Loavsz Local Lemma The repulsive lattice gas is an important model in equilibrium statistical mechanics, and has been studied extensively by mathematical physicists. In the special case of a hardcore nearestneighbor exclusion (i.e. no pair of adjacent sites can be simultaneously occupied), the partition function of the lattice gas on a graph coincides with the independentset polynomial. Much effort has been devoted to finding regions in the complex plane in which this function is nonvanishing The Lovasz Local Lemma is a valuable tool in probabilistic combinatorics for estimating the probability that none of a collection of "bad" events occurs. It applies when dependence between events can be controlled by a "dependency graph", and is useful when the graph is very sparse. In this talk, which presents joint work with Alan Sokal, I will examine a connection between these two apparently disparate subjects. I will discuss closely related results of Shearer in probabilistic combinatorics and of Dobrushin in mathematical physics, as well as a "soft" generalization of the Lovasz Local Lemma. 
INI 1  
11:00 to 11:30  Coffee  
11:30 to 12:00 
S Janson ([Uppsala]) Zeros of truncated binomial polynomials We study the set of zeros of the truncated binomial polynomials \sum_{k=0}^r \binom{n}{k} z^k and \sum_{k=r+1}^n \binom{n}{k} z^k as n and r tend to infinity with r/n converging to some number a, and show convergence of the zero sets to parts of a certain curve in the complex plane. This is joint work with Alex Scott and Alan Sokal. 
INI 1  
12:30 to 13:45  Lunch at Churchill College  
14:00 to 15:00 
R Shrock ([SUNYStony Brook]) Zeros of chromatic and Tutte (Potts) polynomials and general Ising model, and their accumulation sets for families of graphs We discuss results on zeros of chromatic and Tutte polynomials (the latter being equivalent to the Potts model partition function ) in the q and temperature plane, and their accumulation sets for various families of graphs. We also present results on zeros of the q=2 Ising case in the presence of a nonzero magnetic field. This area combines combinatorics and graph theory with complex analysis and algebraic geometry, as well as statistical physics. A numer of areas for further research are suggested. 
INI 1  
15:00 to 15:30  Tea  
15:30 to 16:00 
Zeros of graphcounting polynomials and their accumulation sets We present zeros of several graphcounting polynomials, including flow polynomial F(G,q), reliability polynomial R(G,p) and Jones polynomial. For both flow and reliability polynomials, we consider, among others, square, triangular and honeycomb lattice strips with various fixed widths and arbitrarily great lengths with several different boundary conditions. We study the zeros of F(G,q) and R(G,p) in the complex q and p planes, respectively, and determine exactly the asymptotic accumulation sets of these zeros in the infinitelength limit. We calculate Jones polynomials for several families of alternating knots and links by computing the Tutte polynomials T(G,x,y) for the associated graphs G. For each of these families we determine the zeros of the Jones polynomial and the accumulation set in the limit of infinitely many crossings. A discussion will be given to the calculation of Jones polynomials for nonalternating links. We also calculate exactly the partition function Z(G,Q,v) of the Qstate Potts model for strip graphs with Q and temperature variable v restricted to satisfy conditions corresponding to the ferromagnetic phase transition on the associated twodimensional lattices. In the infinitelength limit, we determine the continuous accumulation loci of the partition function zeros in the v and Q planes. General features of these loci are discussed and conjectures are given for properties applicable to arbitrarily large width. Finally, we present the zero distributions of the Qstate Potts model partition function for large Q, and show when these zeros take on approximately circular patterns in a complex plane. 
INI 1  
16:00 to 16:30 
Chromatic zeros for some recursively defined families of graphs We consider some infinite families of recursively defined graphs. The explicite formulas for chromatic polynomials of graphs from the families will be presented. We study the problem of the location of their complex zeros. 
INI 1  
16:30 to 17:00 
Selfdual spin systems, zeros of partition function, and error correcting codes A new infinite class of selfdual translation invariant spin ½ systems will be introduced. (Two systems of this class are known to be solvable: BaxterWu triangular model and Union Jack model.) Conjectures about distribution of zeros of partition functions of finite volume systems of this class will be formulated. Numerical and rigorous results supporting the conjectures, and connection with the theory of selfdual cyclic codes, will be discussed. 
INI 1  
19:30 to 23:00  Conference Dinner at Emmanuel College 
10:00 to 11:00 
N Biggs (London School of Economics) Complex roots of chromatic polynomials I shall begin by explaining how the theory of representations of the symmetric group can be applied to the transfer matrix. This leads to explicit formulae for the chromatic polynomials of families of graphs, in which the terms correspond to partitions of positive integers. The formulae are wellsuited to the application of the BerahaKahaneWeiss theorem, describing the limit points of zeros of the polynomials. In simple cases the individual terms can be written explicitly as powers of polynomials, and the resulting limit curves are (parts of) closed curves. In the general case the curves can have endpoints and singularities, and I shall discuss some of the interesting phenomena that can occur. 
INI 1  
11:00 to 11:30  Coffee  
11:30 to 12:30 
J Jacobsen ([ParisSud]) Representations and partition function zeros of the Potts model with and without boundaries We consider the following four classes of models defined on the annulus, listed in order of increasing generality: 1. Restricted height models with face interactions 2. Fullypacked loop models based on the TemperleyLieb algebra 3. TL loop models with one boundary generator 4. TL loop models with two boundary generators All of these are different formulations of the Potts model (Tutte polynomial), where, for classes 3 and 4, spins on the rims of the annulus are required to take a different number of states than bulk spins. We show how each class reduces to the one preceding it, provided that one of its parameters takes particular, magical values. In an appropriate part of the phase diagram, these reductions lead to partition function zeros in the more general model. In particular, the reduction from class 2 to 1 gives zeros of the chromatic polynomial at the Beraha numbers, provided one is inside the socalled BerkerKadanoff phase. 
INI 1  
12:30 to 13:45  Lunch at Churchill College  
14:00 to 14:30 
Dominant traits in the zeros of twovariate twoterminal reliability polynomials Various polynomials appear in graph theory: chromatic polynomials, flow polynomials, allterminal reliability polynomials. All these polynomials are special instances of the Tutte polynomial, and the location of their complex zeros has been actively studied (Biggs, Brown & Colbourn, Chang & Shrock, Royle, Sokal, Welsh, to name but a few). General results have been established for the zeros of recursively defined families of polynomials (Beraha, Kahane, and Weiss): the zeros aggregate asymptotically to sets of algebraic curves and sometimes to isolated points. In this contribution, we address the twoterminal (or endtoend) reliability polynomial Rel2, which corresponds to the connectivity of two sites of a graph. Admittedly, this is no graph invariant. However, instead of using the variable $p$ for the (uniform) probability for correct operation of the edges of the graph, we may now consider two variables $p$ and $\rho$ for the edge and site reliabilities, respectively. For a given graph and a pair of sites, we can study the location of the complex zeros of Rel2($p$,$\rho$) as a function of $\rho$. We present results on a few recursive families of graphs for which the twoterminal reliability polynomial may be computed exactly as a function of $p$,$\rho$ and $n$ (the size of the graph); the associated generating functions have also been derived. The asymptotic (for $n$ going to infinity) location of zeros has been investigated and exhibits:  the usual sets of algebraic curves,  appearing (or disappearing) sets of isolated zeros in some cases,  an expansion of the general structure as $\rho$ goes to 0, which can be described by a power law. The set of zeros also undergoes several structural transitions at specific, critical values $\rho_c$  which are algebraic  as $\rho$ decreases from 1 to 0. More surprisingly, by slightly changing the building blocks of the recursive graphs, we may also numerically observe:  particular values of $\rho$ for which the sets of zeros look much smoother,  existence (or not!) of several prevailing sets of isolated zeros with different symmetries (of orders 3 and 13, for instance),  different ``exploding'' families of algebraic curves with different symmetries and expansion rates, too. Asymptotic, analytical expressions for the above phenomena can actually be deduced from the generating function. 
INI 1  
14:30 to 15:00 
Integer symmetric matrices with spectral radius at most 2.019 All graphs with spectral radius (of their adjacency matrix) at most sqrt(2+sqrt(5)) = 2.05817... are known. In joint work with James McKee, we try to extend this result to general symmetric matrices with integer entries. As is clear from the title, we do not get quite as far. Apart from some trivial examples, all the matrices described by the title are represented by 'charged signed graphs' having adjacency matrices with entries 0,1 or 1. 
INI 1  
15:00 to 15:30  Tea  
15:30 to 16:30  Problem session  INI 1  
18:00 to 19:00  Dinner at Churchill College 