Automatic Generation of Generating Functions for Chromatic Polynomials for Grid Graphs (and more general creatures) of Fixed (but arbitrary!) Width

By Shalosh B. EKHAD, Jocelyn QUAINTANCE, and Doron ZEILBERGER

Dédié à la mémoire de PHILIPPE FLAJOLET ( 1^{er} décembre 1948 - 22 mars 2011)

Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger:

http://www.math.rutgers.edu/~zeilberg/pj.html and arviv.org. Written: March 30, 2011.

Very Important: This article comments on the Maple package

http://www.math.rutgers.edu/~zeilberg/tokhniot/KamaTzviot. Some sample input and out-

put can be gotten from the “front” of this article:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/tzeva.html .

One of the many things done in, or inspired by, the famous INRIA ALGORITHMS PROJECT (http://algo.inria.fr/), the brain child of our beloved guru Philippe Flajolet, was to devise efficient algorithms for computing chromatic polynomials for grid graphs, namely the Cartesian product P_{n} × P_{m} where P_{n} is the path of length n. It is fairly easy to see that for a fixed m, the generating function

F_{m}(z, c) = ∑_{n=0}^{∞} P_{P_{n}×P_{m}}(c)z^{n}

is a rational function of both c and z. The Maple package KamaTzviot automatically computes these rational function for any inputted numeric m. (See procedure GFk(m,t,c) of KamaTzviot).

In fact we do something much more general. For any graph G, KamaTzviot can (explicitly!) compute

F_{G}(z, c) = ∑_{n=0}^{∞} P_{P_{n}×G}(c)z^{n} .

(See procedure GFG(G,t,c) .)

In fact we do something even more general! For any graph G, on m vertices, and for any bipartite (m, m) graph C, let M_{n}(G, C) be the graph on mn vertices where the edges among

1 + im , 2 + im , ... , m + im

mimic the graph G (for i = 0, …, n − 1), and in addition the edges between

1 + im , 2 + im , ... , m + im

and

1 + (i + 1)m , 2 + (i + 1)m , ... , m + (i + 1)m

(0 ≤ i < n − 1) mimic the edges of C, given as a set of (up to m^{2}) ordered pairs {[α, β]}. [α, β] ∈ C means that there is an edge between vertex α + im and vertex β + (i + 1)m for 0 ≤ i < n − 1. Note that when C is the monogamy bipartite graph {[1, 1], …, [m, m]}, where Mr i is connected to Mrs i (but no cheating!), then M_{n}(G, C) reduces to the Cartesian product G × P_{n}.

KamaTzviot can (explicitly!) compute the rational function (of z and c):

F_{G,C}(z, c) = ∑_{n=0} P_{M_{n}(G,C)}(c)z^{n} .

See procedure GFGG(G,C,t,c).

The Method

Of course we use the transfer matrix method, but in a symbolic context. The graph G has m vertices, so it can be legally colored by at most m colors. Let’s label the vertices of G, once and for all, by the integers {1, …, m}, and visualize them from left to right. For each (legal) vertex-coloring of G we can associate a canonical form, by renaming the color of vertex 1, color 1, then the color of the smallest vertex of G that is not colored by color 1, color 2, and then the color of the smallest vertex colored by neither of these colors, color 3, etc.

For example, If the coloring is 351132 then its canonical form is 123314.

Our set of “states” consists of all possible canonical colorings of G. Of course, since G has finitely many vertices, this set is a finite set. (In KamaTzviot this is done by procedure CC(G), CC stands for Canonical Colorings). Note that if G has no edges, then CC(G) is in bijection with the set of set-partitions of {1, …, m}, so an upper bound for the number of states is the Bell number B_{m}.

Suppose that the “bottom” G in M_{n}(G, C) is in a certain state S, and we want to add another “layer” (a copy of C and G) to form M_{n+1}(G, C), and we want the state of the new bottom to be T. In how many ways can we color the new m vertices (namely vertices mn + 1, …, mn + m) with c colors, so that the new coloring is still a legal vertex-coloring? If T is the list [j_{1}, j_{2}, …, j_{m}] (of course j_{1} = 1), let’s call the actual colors colored by these vertices i_{j_{1}}, …, i_{j_{m}} respectively, and suppose that there are k different colors in that last layer, i.e.

{j_{1}, …, j_{m}} = {1, …, k} ,

so that

{i_{j_{1}}, …, i_{j_{m}}} = {i_{1}, …, i_{k}} .

By the definition of “state” any such coloring would not introduce an edge within this last layer connecting vertices with the same color, but we have also to worry about the edges of the last installment of C. If the state S is

[a_{1}, …, a_{m}] ,

and it has s different colors, i,e,

{a_{1}, …, a_{m}} = {1, …, s} ,

then for any edge [α, β] ∈ C, we know, by the construction of M_{n}(G, C), that there is an edge between mn + α and m(n + 1) + β. This entails that i_{j_{β}} can not be a_{α}. So for each and every i_{1}, …, i_{k} there is a set of “forbidden colors”, out of the s colors of layer n. Of course each of i_{1}, …, i_{k} can also be colored in one of the c − s colors that are not used in layer n. Converting the “negative” conditions into “positive” ones, we get the set of permissible colors for each i_{1}, …, i_{k}, including what we called “option 0” (in procedure TS1S2G of our Maple package) that denotes choosing one of the remaining c − s colors. Taking the Cartesian product of the option-sets for each of i_{1}, …, i_{k}, we get atomic events where some of the members of {i_{1}, …, i_{k}} are committed to be one of the s colors of layer n, and the rest are different colors from those c − s colors. If there are γ such “0”s, of course the number of ways of doing it is the polynomial of degree γ in c, γ!\binom{c−s}{γ}. Adding the number of possibilities of all the atomic options would give the matrix-entry connecting state S to state T.

We (or rather the first-named author) does it for each pair of states S and T, building up the transfer matrix completely automatically (in other words, it does the “combinatorial research” all by itself!). Once we have the transfer matrix, Ekhad sets up the obvious set of equations for the generating functions for colorings ending at any given state, solves, (symbolically and automatically!) the resulting set of linear equations (with coefficients that are poynomials of z and c), and then adds them up to get the desired generating function.

Let us conclude with a simple example of the grid graphs P_{3} × P_{n}. Here

Edges(G) = {{1, 2}, {2, 3}} ,
C = {[1, 1], [2, 2], [3, 3]} .

There are two states: 121 and 123. Let’s compute the matrix entry connecting state 123 to 121.

The coloring of the bottom layer is [i_{1}, i_{2}, i_{1}] for different colors i_{1} and i_{2} (chosen between 1 and c).

Because of the edge [1, 1] of C we have the restriction i_{1} ≠ 1.

Because of the edge [2, 2], we have the restriction i_{2} ≠ 2.

Because of the edge [3, 3], we have the restriction i_{1} ≠ 3.

So i_{1} may not be colored with color 1 and color 3, while i_{2} may not be colored with color 2. Going to the positive rephrasing: i_{1} = 2 OR 3 ≤ i_{1} ≤ c AND i_{2} = 1 OR i_{2} = 3 OR 3 ≤ i_{2} ≤ c . Taking the “product” we have the six “atomic” events: i_{1} = 2 AND i_{2} = 1 (1 possibility) OR i_{1} = 2 AND i_{2} = 3 (1 possibility) OR i_{1} = 2 AND 3 ≤ i_{2} ≤ c (1!\binom{c−3}{1} = c − 3 possibilities) OR 3 ≤ i_{1} ≤ c AND i_{2} = 1 (1!\binom{c−3}{1} = c − 3 possibilities) OR 3 ≤ i_{1} ≤ c AND i_{2} = 3 (1!\binom{c−3}{1} = c − 3 possibilities) OR 3 ≤ i_{1} ≤ c AND 3 ≤ i_{2} ≤ c (2!\binom{c−3}{2} = (c − 3)(c − 4) possibilities) . Adding these up gives the matrix entry:

M[123, 121] = 2 · 1 + 3(c − 3) + (c − 3)(c − 4) = c^{2} − 4c + 5 .

We leave to our human readers, as an instructive exercise to test their comprehension of our method, to verify that M[121, 121] = c^{2}−3c+3 , M[121, 123] = c^{3}−6c^{2}+13c−10 , M[123, 123] = c^{3}−6c^{2}+14c−13 . Of course, KamaTzviot can do so much more.

Shalosh B. Ekhad, Jocelyn Quaintance, and Doron Zeilberger, Department of Mathematics, Hill Center-Busch Campus, Rugters University, 110 Frelinghuysen Rd, Piscataway, NJ 08544, USA.

Email: [c/o zeilberg, quaintan, zeilberg]@math.rutgers.edu .