11
$\begingroup$

Let P(n) be the set of polynomials that can occur as the chromatic polynomial of a planar map with n countries. What is known or conjectured about the growth of |P(n)|?

PS: Thanks Gerry and Noam, can I narrow the question this way: is there an exponential lower bound on |P(n)|?

$\endgroup$
  • $\begingroup$ I suppose it's bounded above by the number of planar maps with $n$ countries, and there ought to be good estimates of that in the literature. $\endgroup$ – Gerry Myerson Jun 8 '16 at 23:19
  • $\begingroup$ It feels like there should be a database of planar maps, and then after some work, one could look in oeis.. $\endgroup$ – Per Alexandersson Jun 8 '16 at 23:28
  • $\begingroup$ Indeed there is a big literature on enumeration of planar maps, starting with Tutte's work. Also, it is not exactly what the question is asking for, but Tutte's "On the enumeration of four-colored maps" (dx.doi.org/10.1137/0117044) is somewhat relevant. $\endgroup$ – Noam Zeilberger Jun 9 '16 at 7:16
  • 2
    $\begingroup$ @DavidTreumann If you drop the planarity condition, A245883 gives the number of distinct chromatic polynomials among all connected graphs on n nodes. $\endgroup$ – Noam Zeilberger Jun 9 '16 at 20:30
  • 1
    $\begingroup$ @DavidTreumann: This will approach will give all chromatic polynomials of (simplicial) planar triangulations, since Whitney showed that a 4-connected planar triangulation has a Hamiltonian cycle. One can use this to show that planar triangulations have the same chromatic polynomial as one with a Hamiltonian cycle, so coming from gluing ideal triangulations of two $n$-gons. One curious thing is that one can determine a triangulation of an $n$-gon by pairing it with the $n$ triangulations of an $n$-gon which cone to a vertex, and then taking the chromatic polynomials. $\endgroup$ – Ian Agol Jan 31 '17 at 23:24
12
$\begingroup$

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:

elements of $\mathcal{C}_3$

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

deletion-contraction

and a relation to eliminate loops and kill diagrams with bridges

enter image description here

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:

trace of an element in $\mathcal{C}_3$

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:

Tutte relation

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

enter image description here

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:

A,B,e_1,e_2

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:

enter image description here

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks Ian. I'm not sure I get it. There are $3^v$ $3$-colorings of the graph with no edges, and some planar graphs have $0$. Are you saying that, if only a polynomial-sized chunk of the interval $[0,3^v]$ could occur as the number of 3-colorings of a graph on $v$ vertices, it might allow for too fast of an algorithm to determine that a graph was $3$-colorable? $\endgroup$ – David Treumann Jun 9 '16 at 19:39
  • $\begingroup$ No. What I'm trying to say is that most (or exponentially many) of the interval $[0,3^v]$ ought to be realized. The point is to try to translate this into proving a similar thing for 3-SAT. I think that the translations roughly preserve the number of colorings/formulae satisfactions. And it seems more plausible to me that the number of 3-satisfactions of formulae ought to be exponential in the number of variables (although maybe this is just as hard as your question). $\endgroup$ – Ian Agol Jun 9 '16 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.