Skip to content

Workshop Programme

for period 21 - 25 January 2008

Zeros of Chromatic, Flow and Other Polynomials

21 - 25 January 2008

Timetable

Monday 21 January
08:30-09:55 Registration
09:55-10:00 Welcome - David Wallace
10:00-11:00 Sokal, A (New York)
  Complex zeros of the chromatic and Tutte polynomials Sem 1
 

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 Lee-Yang 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 Brown-Colbourn conjecture on zeros of reliability polynomials is false

arXiv:math/0202034 [math.CO] Young-Bin Choe, James G. Oxley, Alan D. Sokal, David G. Wagner Homogeneous multivariate polynomials with the half-plane property

arXiv:cond-mat/0012369 [cond-mat.stat-mech] Alan D. Sokal Chromatic roots are dense in the whole complex plane

arXiv:cond-mat/9904146 [cond-mat.stat-mech] Alan D. Sokal Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions

 
11:00-11:30 Coffee
11:30-12:30 Jackson, B (QMUL)
  Real zeros of chromatic and flow polynomials Sem 1
 

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]

 
12:30-13:45 Lunch at Churchill College
14:00-15:00 Thomassen, C (Technical University of Denmark)
  Chromatic polynomials and a second Hamiltonian cycle Sem 1
 

The chromatic polynomial was introduced by Birkhoff in 1912 in order to study the 4-Color 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 list-chromatic polynomial will be discussed.

 
15:00-15:30 Tea
15:30-16:00 Alikhani, S (Inspem, University Putra Malaysia)
  Chromatic roots and fibonacci numbers Sem 1
 

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 2n-anacci constants and all natural powers of them cannot be root of any chromatic polynomial. Finally, we introduce new numbers related to n-annaci numbers and ask a question similar to Beraha question.

 
16:00-16:30 Morgan, K (Monash)
  Chromatic factorisation of graphs Sem 1
 

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.

 
16:30-17:30 Welcome Wine Reception
18:00-19:00 Dinner at Churchill College
Tuesday 22 January
10:00-11:00 Royle, G (Western Australia)
  Constructive resolution of two conjectures on real chromatic roots Sem 1
 

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.

 
11:00-11:30 Coffee
11:30-12:00 Brown, J (Dalhousie)
  On the zeros of independence and open set polynomials Sem 1
 

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.

 
12:00-12:30 Markstrom, K (Umea)
  Bounds for the numner of matchings in regular graphs Sem 1
 

In this talk I will first present a group of conjectures on the number of k-edge 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.

 
12:30-13:45 Lunch at Churchill College
14:00-15:00 Dong, FM (Nanyang Technological)
  On graphs whose chromatic polynomials have no zeros in (1,2) Sem 1
 

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 zero-free. Jackson conjectured in 1993 that every 3-connected non-bipartite graph has no chromatic zeros in (1, 2). It was recently disproved by Royle’s discovery of some counter-examples. 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 2-connected 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 non-empty independent sets S in G. We observed that, up to now, all 2-connected 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).

 
15:00-15:30 Tea
15:30-16:00 Winkler, J (Sheffield)
  New methods for solving high degree polynomial equations that have multiple roots Sem 1
 

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 non-linear 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 non-linear least squares in Stage 2 is performed by the Gauss-Newton iteration.

Examples will be given to illustrate the success of the method.

 
16:00-16:30 Faris, WG (Arizona)
  The calculus of combinatorial constructions and Hopf algebras Sem 1
 

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.

 
18:00-19:00 Dinner at Churchill College
Wednesday 23 January
10:00-11:00 Fernandez, R (Rouen)
  Cluster expansions for hard-core systems: I introduction Sem 1
 

CLUSTER EXPANSIONS FOR HARD-CORE SYSTEMS: I INTRODUCTION

The talk will be an introductory presentation of cluster expansions for models with self and nearest-neighbour 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 HARD-CORE 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.

 
11:00-11:30 Coffee
11:30-12:30 Fernandez, R (Rouen)
  Cluster expansions for hard-core systems: II convergence criteria Sem 1
 

CLUSTER EXPANSIONS FOR HARD-CORE SYSTEMS: I INTRODUCTION

The talk will be an introductory presentation of cluster expansions for models with self and nearest-neighbor 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 HARD-CORE 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.

 
12:30-13:45 Lunch at Churchill College
14:00-14:30 Zahradnik, M (Charles)
  A simple resummation method for cluster expansions Sem 1
 

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 (Kramers-Wannier representation of the Ising model, perturbations of massless Gaussians) also in several cases where expansions are only nonabsolutely summable.

 
14:30-15:00 Wagner, D (Waterloo)
  Enumeration of spanning subgraphs with degree constraints Sem 1
 

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 Heilmann-Lieb 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 half-plane property and the Grace-Walsh-Szego 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.

 
15:00-15:30 Tea
15:30-16:00 Holtz, OV (Berkeley)
  On polynomials arising from zonotopal algebra Sem 1
 

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

 
16:00-16:30 Sarmiento, I (Roma Tor Vergata)
  The topological Tutte polynomials of Bollobas and Riordan: properties and relations to other graph polynomials Sem 1
 

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 Bouchet’s Tutte-Martin 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].

 
16:30-17:30 Borcea, J (Stockholm)
  Geometry of polynomials and applications Sem 1
 

We discuss closely related geometric properties of zero sets of multivariate polynomials such as real stability, the half-plane 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 half-plane 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

 
18:00-19:00 Dinner at Churchill College
Thursday 24 January
10:00-11:00 Scott, A (Oxford)
  Independent sets, lattice gases and the Loavsz Local Lemma Sem 1
 

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 hard-core nearest-neighbor 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 independent-set 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.

 
11:00-11:30 Coffee
11:30-12:00 Janson, S (Uppsala)
  Zeros of truncated binomial polynomials Sem 1
 

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.

 
12:30-13:45 Lunch at Churchill College
14:00-15:00 Shrock, R (SUNY-Stony Brook)
  Zeros of chromatic and Tutte (Potts) polynomials and general Ising model, and their accumulation sets for families of graphs Sem 1
 

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.

 
15:00-15:30 Tea
15:30-16:00 Chang, S-C (Cheng Kung)
  Zeros of graph-counting polynomials and their accumulation sets Sem 1
 

We present zeros of several graph-counting 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 infinite-length 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 non-alternating links. We also calculate exactly the partition function Z(G,Q,v) of the Q-state Potts model for strip graphs with Q and temperature variable v restricted to satisfy conditions corresponding to the ferromagnetic phase transition on the associated two-dimensional lattices. In the infinite-length 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 Q-state Potts model partition function for large Q, and show when these zeros take on approximately circular patterns in a complex plane.

 
16:00-16:30 Bielak, H (Maria Curie-Sklodowska)
  Chromatic zeros for some recursively defined families of graphs Sem 1
 

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.

 
16:30-17:00 Slawny, J (Virginia Tech)
  Self-dual spin systems, zeros of partition function, and error correcting codes Sem 1
 

A new infinite class of self-dual translation invariant spin ½ systems will be introduced. (Two systems of this class are known to be solvable: Baxter-Wu 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 self-dual cyclic codes, will be discussed.

 
19:30-23:00 Conference Dinner at Emmanuel College
Friday 25 January
10:00-11:00 Biggs, N (London School of Economics)
  Complex roots of chromatic polynomials Sem 1
 

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 well-suited to the application of the Beraha-Kahane-Weiss 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 end-points and singularities, and I shall discuss some of the interesting phenomena that can occur.

 
11:00-11:30 Coffee
11:30-12:30 Jacobsen, J (Paris-Sud)
  Representations and partition function zeros of the Potts model with and without boundaries Sem 1
 

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. Fully-packed loop models based on the Temperley-Lieb 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 so-called Berker-Kadanoff phase.

 
12:30-13:45 Lunch at Churchill College
14:00-14:30 Tanguy, C (Orange Labs)
  Dominant traits in the zeros of two-variate two-terminal reliability polynomials Sem 1
 

Various polynomials appear in graph theory: chromatic polynomials, flow polynomials, all-terminal 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 two-terminal (or end-to-end) 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 two-terminal 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.

 
14:30-15:00 Smyth, C (Edinburgh)
  Integer symmetric matrices with spectral radius at most 2.019 Sem 1
 

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.

 
15:00-15:30 Tea
15:30-16:30 Problem session
18:00-19:00 Dinner at Churchill College

Back to top ∧