Algebraic properties of chromatic roots

It has been a long time coming. I wrote back in 2011 about the work Kerri Morgan and I were doing on algebraic properties of chromatic roots. A paper has just gone on the arXiv.

I will just recap here, and mention some of the most interesting things we can’t do.

The chromatic polynomial of a graph is a monic integer polynomial whose value at a positive integer q is the number of proper colourings of the vertices with q colours (so that no two adjacent vertices get the same colour). A chromatic root is a complex number which is the root of a chromatic polynomial.

Thus, chromatic roots are algebraic integers. But not every integer is a chromatic root. All non-negative integers are (since the complete graph on n vertices has roots 0,1,…n−1), but no negative integer is.

More generally, if α is a chromatic integer, then so is α+n for any natural number n (take the “join” of the graph realising α with a complete graph on n vertices). Our big open problem is the converse:

Problem: Is it true that, for every algebraic integer α, there exists a natural number n such that α+n is a chromatic root?

There is only one known technique for showing that an algebraic integer is not a chromatic root. There are no negative chromatic roots, none in the interval (0,1), and none in the interval (1,32/27]. (The last remarkable fact was proved by Bill Jackson, and Carsten Thomassen showed that it cannot be improved, since chromatic roots are dense in [32/27,+∞).) Thus, if an algebraic number has a conjugate in one of these forbidden intervals, then it is not a chromatic root either.

The classic example involves the golden ratio α = (−1+√5)/2. This is not a chromatic root, since it lies in (0,1). Also, both α+1 and α+2 have conjugates in a forbidden interval. It is not known whether or not α+3 is a chromatic root. (Resolving this would involve the introduction of new techniques which would no doubt help in other cases!) But α+4 is a chromatic root (the smallest graph representing it has 8 vertices).

Our main technique is to study families of graphs for which the chromatic polynomial is a product of a number of linear factors together with one “interesting” factor. Computation shows that this interesting factor is very often irreducible. If we can find a family containing infinitely many graphs such that the degree of the “interesting” factor is bounded by k, then we have a chance of realising many algebraic integers of degree k as chromatic roots.

Two such families of graphs are known. One consists of rings of cliques (one of these is a union of k+2 cliques arranged in a ring such that adjacent cliques are completely joined) in which one of the cliques has size 1. The interesting factor is obtained by taking the monic polynomial whose roots are the sizes of the cliques (excluding one of size 1), removing the constant term, and dividing by x. Thus, for example, for a ring of four cliques with sizes 1,1,1,5, the “interesting” factor is x2−7x+11, which has the golden ratio plus 4 as a root.

The other such family consists of bicliques (the disjoint union of two cliques with arbitrary extra edges): the degree of the “interesting factor” is the size of the smaller clique. Thus the ring of cliques in the preceding paragraph is also a biclique where the cliques have sizes 2 and 6.

Using this, we proved the α+n conjecture for quadratic integers (with thanks to David Wallace, director of the Isaac Newton Institute at the time, for his contribution), and subsequently Adam Bohn proved it for cubic integers.

Another question is very specific, but our inability to solve it might be thought to cast doubt on the α+n conjecture:

Problem: Is there an irreducible factor of a chromatic polynomial whose Galois group is the cyclic group of order 5?

We have realised all transitive groups of degree up to 4, and all the other transitive groups of degree 5, as Galois groups, but the cyclic group of order 5 eludes us. Shifting a root does not change the Galois group, of course, so if the α+n conjecture is true then such a factor would have to exist. Indeed, the only realisations of cyclic groups of order greater than 4 that we have found are those of order p−1, for a prime p, realised by the cycle of length p+1.

A third problem involves random graphs. Bollobás showed that the chromatic number of a random graph on n vertices is tightly concentrated around n/(2 log n). So the chromatic polynomial of such a graph has at least this many linear factors: there may be more, since there may be repeated roots.

Problem: Is it true that, with high probability, the chromatic number of a random graph on n vertices is the product of linear factors and a single “interesting” factor which is irreducible and whose Galois group is the symmetric group of the appropriate degree? If so, what is the typical degree?

And a final, more general question:

Problem: Find other infinite families of graphs for which the chromatic polynomial is the product of linear factors and an “interesting” factor of bounded degree.

Rings of cliques have just enough parameters to possibly prove the α+n conjecture, with one to spare. Bicliques have exponentially many parameters, so that it is extremely difficult to spot a good specialisation to do the job.
Another family might help us here.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s