This post is a description of the problem I was working on at Monash, algebraic properties of chromatic roots, with some background and history, and a bit about the progress we made on it. It is by no means a complete survey of what we did; it is more about the origin of the problem.
History and background
A proper colouring of a graph G is an assignment of colours to the vertices of G in such a way that adjacent vertices receive different colours. Apart from the well-known connection with colouring maps, a typical application is to radio frequency assignment: colours are frequencies, and two transmitters which are physically close together cannot use the same frequency.
Birkhoff, in an attack on the Four-Colour Conjecture as it was then (asserting that a graph which can be drawn in the plane without crossing edges can be properly coloured with four colours) nearly 100 years ago, made the following observation: the number of proper colourings of a graph G with q colours is the evaluation at x=q of a polynomial P(G;x), now called the chromatic polynomial of G. It is a monic polynomial with integer coefficients, of degree equal to the number of vertices of G, and with constant term zero; the coefficients alternate in sign.
The chromatic polynomial of a graph has another interpretation in statistical mechanics, where it is a trivial renormalisation of the partition function of the q-state Potts model based on the graph. I won’t explain the connection here; the point of this is to explain the interest of physicists in this polynomial, which had a big influence on subsequent developments.
Once we have a polynomial, it is natural to look at its roots. This is the primary interest of the physicists, for whom the limit points of roots of chromatic polynomials may give information about phase transitions of an infinite physical system. A lot is known about the location of the roots:
- The integer roots of P(G,x) are precisely the integers in the interval [0,χ(G)−1], where χ(G) is the chromatic number of G. (It is clear that these integers are roots since, byy definition, the number of colourings with q colours is zero if 0≤q<χ(G). Also by definition, there are no larger integer roots; and since the coefficients alternate, the value of the polynomial is non-zero with sign (−1)n for negative values of the argument.)
- Since P(G;x) is a monic polynomial with integer coefficients, it has no non-integer rational roots.
- As in the first item, there are no negative real roots. Bill Jackson showed that there are no real roots in the interval (0,32/27) apart from 1; Carsten Thomassen showed, in the other direction, that real roots of chromatic polynomials are dense in [32/27,∞): that is, there are graphs whose chromatic polynomials have roots arbitrarily close to any given real number at least 32/27.
- Alan Sokal showed that complex roots of chromatic polynomials are dense in the complex plane. In fact, he showed that chromatic roots of theta-graphs Θ(s,p) are dense outside the circle of radius 1 and centre −1. Here Θ(s,p) is the graph consisting of p disjoint paths of length s with their end points identified. Now there is a simple trick (see below) to shift the roots of a chromatic polynomial by a positive integer; so the whole plane is covered.
At the Isaac Newton Institute
In 2008, the Isaac Newton Institute hosted a six-month programme on Combinatorics and Statistical Mechanics, at which all the people mentioned in the last section (except Birkhoff) were present. The director of the INI at the time was Sir David Wallace; his background is in statistical mechanics, but, finding his time not completely taken up with running the Institute and Churchill College, he was teaching himself Galois theory from Ian Stewart’s book.
At some point during the programme, he said to us, “You guys are interested in roots of polynomials; is anything known about their algebraic properties, such as factorisation, splitting fields, Galois groups?” It turned out that very little was known in general, so we started a weekly study group on this, bringing in Vladimir Dokchitser as a “tame number theorist” to help out. David took part in the study group, and indeed came up with a proof of a case of one of our conjectures, as I will explain below.
Also at the meeting for various periods were Graham Farr and his student Kerri Morgan, who was writing a thesis about factorisation of chromatic polynomials, and in particular when one can produce a “certificate” (hopefully of polynomial length) guaranteeing that the chromatic polynomial of a certain graph has a factorisation. Often such a certificate takes the form of a proof that the graph has the same chromatic polynomial as another graph, for which the factorisation is obvious.
Let us say that a chromatic root is a complex number which is a root of the chromatic polynomial of some graph. Since any chromatic root is the root of a monic polynomial with integer coefficients, it is necessarily an algebraic integer.
The set of chromatic roots is not closed under either addition or multiplication. For, by Sokal’s result, there is a non-real chromatic root α with negative real part and modulus less than 1; if β is its complex conjugate, then neither α+β nor αβ is a chromatic root, since both are real and the first is negative while the second is between 0 and 1.
However, if α is a chromatic root, then so is α+n, for any positive integer n. For, if α is a chromatic root of the graph G, then add n new vertices joined to one another and to every vertex of G; the new graph H satisfies P(H;x) = x(x−1)…(x−n+1)P(G;x−n).
Our first conjecture was a converse of this result. We called this the “α+n conjecture”.
For any algebraic integer α, there is a natural number n such that α+n is a chromatic root.
In the INI study group, we proved this in the case where α is a quadratic integer (a root of a monic quadratic polynomial with integer coefficients), and subsequently Adam Bohn has proved it for cubic integers α.
The other conjecture is based on the observation that, for many special graphs, there is a simple construction (involving blowing up some vertices into cliques) such that, if α is a chromatic root of the given graph, then nα is a chromatic root of the new graph. Again we conjecture a converse, the “nα conjecture”.
If α is a chromatic root, then so is nα for every positive integer n.
What happened next?
Two things happened which were important to the investigation.
First, Graham Farr applied for an Australian Research Council Discovery grant to investigate the problem. The grant involved Daniel Delbourgo (a number theorist also at Monash), Kerri Morgan (as a post-doc to work on the project), Bill Jackson and me (as “partner investigators”). Graham patiently shepherded the team through the baroque application procedure, and the application was successful.
Second, Adam Bohn showed up in my office, having abandoned a PhD in the USA to come back to Britain, to discuss whether he might do one at Queen Mary. By good fortune, we had one free studentship, so we were able to take him on. After some discussion, he decided to work on this and related questions.
The ARC paid Adam’s fares to Melbourne a couple of months ago, and then mine for this trip.
A typical chromatic polynomial
I have to say that what we achieved during my time at Monash was not so much proofs of theorems but rather the discovery of new and extraordinary phenomena which cry out for explanation.
First, another conjecture about chromatic polynomials. This one is less supported than the other two, and is consequently less precise. It is really an attempt to answer the question: what does the chromatic polynomial of a “typical” graph look like?
According to Hilbert, a “typical” polynomial is irreducible in the strongest possible sense: its Galois group is the symmetric group (so, as I discussed in an earlier post, solving the polynomial involves the maximum amount of work). This cannot be true of chromatic polynomials, since we know that the integers between 0 and χ(G)−1 (inclusive) are roots of P(G;x). Indeed, these roots may (and often do) have multiplicity greater than one.
So here is a wild conjecture and a problem. First, the conjecture:
The chromatic polynomial of a random graph is (with high probability) the product of linear factors and a single irreducible factor whose Galois group is the symmetric group.
And the problem:
If the preceding conjecture is true, what is the degree of the irreducible factor? (It is known that the chromatic number is very tightly concentrated; but because the linear factors may have multiplicities, it does not follow that the degree is n minus the typical chromatic number.)
We call the residue after the linear factors have been removed the “interesting factor” of the chromatic polynomial.
Sometimes we take a slightly different view. It sometimes happens that the chromatic polynomial is divisible by one or more shifted cyclotomic polynomials. Sometimes we regard these as being trivial too, and cancel them as well before obtaining the “interesting factor”. Below, I won’t do this without a warning.
Note in passing that the chromatic polynomial of the cyclic graph on n vertices is (x−1)((x−1)n-1−(−1)n-1). Its splitting field is the (n−1)st cyclotomic field, and its Galois group is the multiplicative group of the integers modulo n−1.
Recall that chromatic equivalence of graphs means that they have the same chromatic polynomial. We define splitting-field equivalence to mean that their chromatic polynomials have the same splitting field. The truth of the α+n conjecture would imply that every algebraic number field field is contained in the splitting field of some chromatic polynomial.
In questions about splitting-field equivalence, it is often convenient to treat chromatic equivalence as a “black box”.
Adding or removing linear factors does not change the splitting field. If two graphs have the same interesting factor, we can make them chromatically equivalent by tinkering with the linear factors. (The chromatic polynomial of the complete graph on k vertices is x(x−1)…(x−k+1), so by adding suitable complete graphs to each of the given pair we can make the linear factors match.) Moreover, we already saw how to shift the chromatic polynomial by adjoining vertices joined to everything; so, if the interesting factors are shifts of each other, again we can easily make the graphs chromatically equivalent. Once this is done, Kerri’s results imply that we can find a certificate for this equivalence.
Empirically, we found several curious and unexplained facts about the interesting factors of small splitting-field equivalent graphs. For a start, almost always they are either shifts (g(x)=f(x−k)) or reflections (g(x)=f(k−x)) of each other. (If two cubic integers have generate the samme field, then typically each is a quadratic expression in the other; but we found almost no examples where the expression was not linear.)
So the problem we faced was: is there a general graph-theoretic construction which results in reflection of the interesting factor? The only example we knew was one found by Adam Bohn, which led him to the proof of the α+n conjecture in the cubic case. A biclique is a graph consisting of two disjoint cliques with possibly some edges between them. The operation of complementing the edges between the bicliques reflects the interesting factor of the chromatic polynomial. (We think we are on the track of an operation acting on more general classes of graphs…)
Adam’s results imply that, given any cubic polynomial, some shift of it is the interesting factor of the chromatic polynomial of a biclique. So a certificate for reflection in this case would be: take the first graph, find a biclique whose interesting factor is a shift of the interesting factor of the cubic, “complement” it, and show that this is equivalent to the second graph.
The fly in the ointment was a bit unexpected. The smallest biclique given by Adam’s procedure whose interesting factor is a shift of the polynomial x3−2 has over three thousand vertices! So it is not clear how feasible the above program is.
Another remarkable observation we made about small splitting-field equivalent graphs was that, in every case we considered, the graphs had non-trivial symmetry, sometimes quite a lot of symmetry. The two observations about these graphs (that the interesting factors are shifts or reflections of each other, and that the graphs have symmetry) demand an explanation!
Yet another special feature. If you choose two quartic polynomials with the same splitting field and with Galois group dihedral of order 8, then half the time one will have a linear factor over the field generated by a root of the other, and half the time it will be a product of two quadratics. (This is because the dihedral group has two conjugacy classes of core-free subgroups of index 4.) But among quartic interesting factors for small graphs, we didn’t find a single instance of the second type of behaviour.
We did various further things, most of which I won’t describe here.
When I arrived, Kerri and Daniel had been trying to work out a formula for the discriminant of the interesting factor of the chromatic polynomial of a theta-graph. The formula has a lot of terms, which are shown in the illustration below. We spotted some patterns in them (they form two Pascal-like triangles, and we could compute the entries on the boundaries of the triangles, but not the rule – if there is one – for generating each entry from the ones above).