How many chromatic polynomials of planar maps are there?

The following post has now been written up as Section 6 of this paper. In fact, one may show that the number of values of the chromatic polynomials at 4 grows exponentially.

The number of chromatic polynomials grows exponentially. This answer is joint with Slava Krushkal.

The Chromatic algebra $\mathcal{C}_n$ is an algebra over $\mathbb{C}[Q]$ (for a parameter $Q$) formed from linear combinations of (isotopy classes of) planar graphs in a rectangle $R$ with $n$ univalent points on top and bottom:

Such diagrams may be composed by placing one on top of the other, fusing the $n$ univalent vertices together to get edges. Then quotient this algebra by some relations: the deletion-contraction relation

and a relation to eliminate loops and kill diagrams with bridges

Such diagrams represent planar graphs which agree outside of the shown pictures. These relations are satisfied by the polynomial in $Q$ which counts the number of nowhere zero flows (over an abelian group with $Q$ elemnts) in a graph. There is also a trace, where one closes up the graph top to bottom and evaluates the flow polynomial:

For generic $Q\in \mathbb{C}$, this is a semisimple algebra. More generally, one can describe a planar algebra containing all of the $\mathcal{C}_n$s.

To understand why the number of chromatic polynomials grows exponentially, the idea is to take some graphs in $\mathcal{C}_n$ which generate a semigroup in the algebra. Since the algebra is linear, the Tits alternative for semigroups implies that either this semigroup should contain a free subsemigroup or is virtually nilpotent. The latter is unlikely, if one takes generators of $\mathcal{C}_n$, since it is semisimple. Hence, the growth of the elements in the algebra when one multiplies these generators is exponential. Then one may extract the matrix entries by multiplying with a basis of $\mathcal{C}_n$ and taking traces (to get inner products with the basis, and hence essentially the entries of the matrix). The number of these traces grows exponentially, hence the number of flow polynomials of the graphs (hence the chromatic polynomials of the dual planar graphs) as a function of the number of vertices.

For concreteness, we have an explicit example to demonstrate this approach. We want the smallest dimension subalgebra possible, so it's convenient to set $Q=\phi+1 = \frac{3+\sqrt{5}}{2}$ since $\mathcal{C}_n$ then has a non-trivial trace radical generated by the Tutte relation:

For trivalent (cubic) graphs, it is convenient to use this form of the relation:

Adding this relation (which doesn't affect the value of the flow polynomial for planar graphs at $Q=\phi+1$) decreases the dimension of the algebra, and hence makes it easier to compute with.

We'll do a variation on the above strategy. Consider the elements $A, B$ of $\mathcal{C}_3$ in this picture:

We can multiply (by stacking) $A$ and $B$ with the graphs $e_1, e_2$, which are not elements of $\mathcal{C}_3^{\phi+1}$, but of a related vector space $\mathcal{C}_{3,1}$ which is a module over $\mathcal{C}_3$ (really in the planar algebra), for $Q=\phi+1$ (obtained the same way by taking graphs modulo the deletion-contraction relations). Then we may compute $Ae_1= -\phi e_1, Ae_2=-\phi^2 e_2-\phi e_1,$ $Be_1=-\phi^2 e_2-\phi e_1, Be_2=-\phi e_2$, so the action of $A,B$ preserves the subspace spanned by $e_1,e_2$. These are represented by the matrices:

$A=\left(\begin{array}{cc}-\phi & -\phi \\0 & -\phi^2\end{array}\right),$ $B=\left(\begin{array}{cc}-\phi^2 & 0 \\-\phi & -\phi\end{array}\right),$

Now, multiply $A, B$ together $n$ times, getting $2^n$ elements of $\mathcal{C}_3$. Then add on $e_1, e_2$ on bottom, and their reflections on top, to get an element of $\mathcal{C}_1$. Then take the trace, so connect by an arc running from top to bottom, and evaluate the flow polynomial. The graphs $A,B$ then have a subsemigroup in $GL(2,\mathbb{R})$ which is free (since they have distinct eigenvectors), so the various products give distinct elements of $\mathcal{C}_3$, and hence we get at least $2^{n/4}$ distinct coefficients when we pair with the $e_i$s and take the trace.

Here's $ABAAB$ capped off one way:

I suspect the answer to this question ought to be yes, there should be an exponential lower bound on $|P(n)|$. In fact, I think there ought to be an exponential lower bound on the number of 3-colorings of planar graphs with $n$ vertices. I don't know how to prove this, but some evidence is that 3-colorability of planar graphs is NP-complete. This is proven by reducing 3-colorability of general graphs to that of planar graphs. In turn, 3-SAT is shown to reduce to 3-colorability, by constructing for each formula a graph which is 3-colorable iff the formula is satisfiable. Now, the number of 3-satisfactions of formulas ought to grow exponentially, I think. And the more satisfactions a formula has, the more colorings the corresponding graphs have. So the number of 3-colorings of planar graphs out to grow exponentially, and hence the number of chromatic polynomials. Anyway, this at least heuristically predicts that there ought to be exponential growth of the number of polynomials.