The n-Category Café

Allen wrote:

Rota wrote:

The minimum number of colors required to properly color a map is given by the roots of a polynomial, called the chromatic polynomial; its value at N tells you in how many ways you can color the map with N colors.

Perhaps I’m only showing my naivete, but I’m not sure what the roots have to do with anything. As he says only a moment later, the natural interest is in the values at natural numbers.

Probably Rota just meant that there are no ways to N-color a map (or really a graph) if its chromatic polynomial vanishes at N. Using this, we can in principle figure out the minimum number of colors required.

Rota was probably talking this way just to be comprehensible by layfolk while still sounding really cool.

But, there are weirdly interesting questions about the non-integral roots of the chromatic polynomial! From week22:

Consider the problem of trying to color the vertices of a graph with $n$ colors in such a way that no two vertices at opposite ends of any given edge have the same color. Let $P(n)$ denote the number of such n-colorings. This turns out to be a polynomial in $n$ - it’s not hard to see using recursion relations similar to the skein relations above. It also turns out that the 4-color theorem is equivalent to saying that the vertices of any planar graph can be 4-colored. (To see this, just use the idea of the “dual graph” of a graph - the vertices of the one being in 1-1 correspondence with the edges of the other.) So, another way to state the 4-color theorem is that for no planar graph does the polynomial $P(n)$ have a root at $n = 4$.

$P(n)$ is called the “chromatic polynomial” and has been intensively investigated. One very curious thing is this. Remember the golden mean

$$\Phi = (\sqrt{5}+ 1)/2 = 1.61803398874989484820458683437...?$$

Well, $\Phi + 1$ is never a root of the chromatic polynomial of a graph! (Unless the polynomial vanishes identically, which happens just when the graph has loops.) The proof is not all that hard, and it’s in Saaty and Kainen’s book.

However — and here’s where things get really interesting — in 1965, Hall, Siry and Vanderslice figured out the chromatic polynomial of a truncated icosahedron. (This looks like a soccer ball or buckyball.) They found that of the four real roots that weren’t integers, one agreed with $\Phi + 1$ up to 8 decimal places! Of course, here one might think the 5-fold symmetry of the situation was secretly playing a role. But in 1966 Barri tabulated a bunch of chromatic polynomials in her thesis, and in 1969 Berman and Tutte noticed that most of them had a root that agreed with $\Phi + 1$ up to at least 5 decimal places.

This curious situation was at least partially explained by Tutte in 1970. He showed that for a triangular planar graph (that is, one all of whose faces are triangles) with $n$ vertices one has

$$|P(\Phi + 1)| \le \Phi^{5-n}$$

This is apparently not a complete explanation, though, because the truncated icosahedron is not triangular.

This is not an isolated freak curiosity, either! In 1974 Beraha suggested checking out the behavior of chromatic polynomials at what are now called the “Beraha numbers”

$$B(n) = 4 cos^2(\pi/n).$$

Note by the way that $B(n)$ approaces 4 as $n$ approaches infinity. It turns out that the roots of chromatic polynomials seem to cluster near Beraha numbers — as if graphs were trying to come really close to being impossible to 4-color!

For example, the four nonintegral real roots of the chromatic polynomial of the truncated icosahedron are awfully close to $B(5), B(7), B(8)$ and $B(9)$. Beraha made the following conjecture: let $P_i$ be a sequence of chromatic polynomials of graphs such whose number of vertices approaches infinity as $i \to \infty$. Suppose $r_i$ is a real root of $P_i$ and suppose the $r_i$ approach some number $x$. Then $x$ is a Beraha number. In work in the late 60’s and early 70’s, Tutte proved some results showing that there really was a deep connection between chromatic polynomials and the Beraha numbers.

Well, to make a long story short (I’m getting tired), the Beraha numbers also have a lot to do with the quantum group $SU(2)$. This actually goes back to some important work of Jones right before he discovered the first of the quantum group knot polynomials, the Jones polynomial. He found that — pardon the jargon burst — the Markov trace on the Temperley-Lieb algebra is only nonnegative when the Markov parameter is the reciprocal of a Beraha number or less than 1/4. When the relationship of all this stuff to quantum groups became clear, people realized that this was due to the special nature of quantum groups when $q$ is an $n$th root of unity (this winds up corresponding to the Beraha number $B(n)$.) This all leads up to a paper that, unfortunately, I have not yet read:

• Zeroes of chromatic polynomials: a new approach to the Beraha conjecture using quantum groups, by H. Saleur, Comm. Math. Phys. 132 (1990) 657.

This apparently gives a “physicist’s proof” of the Beraha conjecture, and makes use of conformal field theory, that is, quantum field theory in 2 dimensions that is invariant under conformal transformations.

This all sounds quite cool, and I wish I knew what became of these ideas later on…

However, while Xiao-Song Lin found fascinating patterns in the roots of the Jones polynomials of random links, Dan Christensen and Igor Khavkine’s work suggests that some of these patterns may simply be due to the polynomials having integer coefficients!

The chromatic polynomial also has integer coefficients. So, maybe some of the Beraha conjecture could be explained simply by that fact??? I have no idea.