Chromatic polynomials II

In this week-late post I will talk some more about results and conjectures concerning chromatic polynomials of graphs and matroids. As the title suggests, this is a continuation from my April post on the same topic. At the end of that post I said that I would discuss complex chromatic roots of graphs, but here I’ve decided to talk about matroids instead.

The chromatic polynomial of graphs is defined in terms of number of colourings with a given number of colours; this definition does not extend to matroids for obvious reasons. However, the Recipe Theorem by Oxley and Welsh in [OW79] tells us that a function on graphs or matroids satisfying a deletion-contraction recursion is essentially an evaluation of the Tutte polynomial. Now the chromatic polynomial does satisfy this type of recursion, and in fact Tutte’s polynomial was first called by Tutte the dichromatic polynomial, since he saw it as a generalisation of the chromatic polynomial of a graph. If $T_G(x,y)$ denotes the Tutte polynomial of a graph $G$, then \[P(G,q)=(-1)^{|V(G)-k(G)}q^{k(G)}T_G(1-q,0).\]

This definition can easily be extended to matroids. However, the equivalent of the chromatic polynomial for matroids is called the characteristic polynomial, and it is very slightly different (in that is has a missing power of $q$ factor). The characteristic polynomial of a matroid $M$ is denoted as $C(M,q)$ and may be defined as \[C(M,q)=(-1)^{r(M)}T_M(1-q,0).\]

So if $G$ is a graph with $k(G)$ components and $M=M(G)$, then $C(M,q)=q^{-k(G)}P(G,q)$, which for our purposes means that the chromatic polynomial of a graph $G$ and the characteristic polynomial of its graphic matroid $M(G)$ are essentially the same. I’m not sure why this terminology was adopted, since the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix, hence has nothing to do with the characteristic polynomial of its graphic matroid. Anyway, let’s see what we can say about real chromatic roots of matroids. We can still talk about root-free intervals and upper root-free intervals in the same way as for graphs.

Just to recap, a real interval $(a,b)$ is a root-free interval for a family of matroids $\mathcal{M}$ if no matroid in  $\mathcal{M}$ has a chromatic root (i.e. a root of its characteristic polynomial) in the interval $(a,b)$, while $\mathcal{M}$ has an upper root-free interval if there is a real number $a$ such that no matroid in $\mathcal{M}$ has a real root larger than $a$. The class of all matroids does not have an upper root-free interval (since you can get arbitrarily large chromatic roots from graphs). Many of the results I mentioned for graphs in my previous post generalise to matroids. In particular, if $M$ is a loopless connected matroid, then:

  • $C(M,q)$ is an alternating polynomial with degree $r(M)$,
  • $C(M,q)$ is non-zero with sign $(-1)^{r(E)}$ for $q\in (-\infty,0)$,
  • $C(M,q)$ has a simple zero at $q=1$, and
  • $C(M,q)$ is non-zero with sign $(-1)^{r(E)+1}$ for $q\in (0,\frac{32}{27})$.

As for graphs, the first three results are easy to see if you write the chromatic polynomial in the right form. Namely

\[C(M,q)=\sum_{X\subseteq E(M)}(-1)^{|X|}q^{r(E)-r(X)}.\]

The fourth result above was proved for matroids by Edwards, Hierons and Jackson [EHJ98]. So the magic number $\frac{32}{27}$ is still magic for matroids.

If a class of matroids contains all graphic matroids, then it has no upper root-free interval (because of cliques). What about minor-closed classes of matroids not containing all graphs?

If you recall, Woodall and Thomassen proved independently that if $\mathcal{G}$ is a proper minor-closed family of graphs, then $(d(\mathcal{G}),\infty)$ is an upper root-free interval for $\mathcal{G}$, where $d(\mathcal{G})$ is the minimum number such that every graph in $\mathcal{G}$ has a vertex of degree at most $d$ (this is finite by a theorem of Mader). The surprising fact is that this result was published in 1997, while it is in fact implied by a more general and quite a bit older result for matroids. In 1978 Oxley proved the following.

Theorem 1: Let $D=\{x_1,\ldots,x_k\}$ be a cocircuit of a matroid $M$. Then \[C(M,q)=(q-k)C(M\backslash D,q)+\sum_{j=2}^{k}\sum_{i=1}^{j-1} C(M\backslash x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_{j-1}/x_i,x_j, q).\]

This looks a bit complicated, but by induction it implies the following.

Corollary 2: If all minors of a matroid $M$ have a cocircuit of size at most $k$, then $C(M,q)>0$ for all $q \geq k$.

Corollary 2 in turns implies that any proper minor-closed class of graphs has an upper root-free interval (i.e. the result of Woodall and Thomassen). It also implies the same result for matroids of bounded branch width. Unfortunately, minor-closed classes of matroids may not have bounded minimum cocircuit size, even if they don’t contain all graphic matroids, so the following is still wide open.

Conjecture 3: Every minor closed class of matroids that does not contain all graphic matroids has an upper root-free interval.

A very special but still very difficult case of this conjecture is the following.

Conjecture 4: The class of cographic matroids has an upper root-free interval.

Conjecture 4 has been studied quite a bit, since it is in fact a question on flows in graphs (the characteristic polynomial of a matroid is the flow polynomial of its dual). I’ll conclude the post with a bit of history on this problem.

Welsh conjecture that $(4,\infty)$ is an upper root-free interval for cographic matroids. For planar graphs this would imply the Birkoff-Lewis conjecture. However, Gordon Royle found counterexamples to this conjecture by looking at a family of graphs called generalised Petersen graphs. Based on the examples he found for which he could calculate the real roots, he modified Welsh’s conjecture, changing the 4 to a 5, as “$(5,\infty)$ is an upper root-free interval for cographic matroids”. However, this conjecture turned out to also be false, as proved by Jesus Salas and Jesper Jacobsen, who managed to show that some large generalised Petersen graph has real flow roots slightly over 5. Incidentally, in July I went to Royal Holloway to attend the Workshop on New Directions for the Tutte Polynomial and I saw Jesus Salas give a talk on this. You can have a look at his slides on the conference page. So now the question remains of whether cographic matroids do have an upper root-free interval, and if so, what the interval is.

References

[O78] J. G. Oxley, Colouring, packing and the critical problem, Quart. J. Math. Oxford Ser. (2), 29(113), pp 11-22, 1978.

[OW79] J. G. Oxley and D. J. A. Welsh, The Tutte polynomial and percolation, Graph Theory and Related Topics (eds. J. A. Bondy and U. S. R. Murty), pp. 329-339, Academic Press, London, 1979.

[EHJ98] H. Edwards, R. Hierons, and B. Jackson, The zero-free intervals for characteristic polynomials of matroids, Combin. Probab. Comput., 7(2), pp. 153-165, 1998.

[JS13] J. L. Jacobsen and Jesús Salas, Is the 5-flow conjecture almost false?, Journal of Comb. Theory Series B, 103(4), pp. 532-565, 2013.

 

Leave a Reply

Your email address will not be published. Required fields are marked *