A Polynomial related to Colourings of Triangulation of Sphere

by Yuri Matiyasevich

This HTML paper is written especially for Personal Journal of Yuri MATIYASEVICH.
The paper is updated when new results are found.
Last essential modifications were done on July 4, 1997.
Last small modifications were done on December 2, 1998.

Let T be a triangulation of a sphere, i.e. a maximal planar graph. It is well-known that the vertices of this graph can be properly coloured in 4 colours if and only if the edges of its plannary dual graph can be properly coloured in 3 colours. Instead of dealing with this dual graph, we will rather consider colourings of edges of triangulation T itself in such a way that the three edges of each triangular face are coloured differently.

With every triangulation T of a sphere we associate a polynomial MT in many variables, coefficients of which are related in several unexpected ways to the number cT of 3-colourings of the edges of the triangulation. Respectively, this allows us to state a number of equivalent reformulations of the famous Four Colour Conjecture (4CC for short).

Let T be a triangulation of a sphere with 2n triangles. Such a triangulation has 3n edges which will be denoted e0,...,e3n-1. Let us enumerate the triangles in some way, and let epk, eqk, erk be the edges of the kth triangle listed in clock-wise order.

Let us associate with each edge ei of the triangulation a formal variable xi, and let us associate with the kth triangle the polynomial Sk equal to

(epk -eqk) (eqk -erk) (erk -epk).

Let NT denote the (auxiliary) polynomial equal to the product of all 2n polynomials Sk. The polynomial NT has degree 4 in each of its variables. Let us reduce it to a polynomial MT of degree 2 in each variable according to the scheme x3-->1, i.e. in each monomial comprising the polynomial NT we delete variables coming in degree 3, and replace the exponent 4 by exponent 1 for variables coming in degree 4 (such a transformation is justified if the values of the variables are assumed to be cubic roots of 1).

The polynomial MT is the sum of 33n monomials of the form

ci0...i3n-1 x0i0... x3n-1i3n-1.

To simplify notation, we will view the multiindex i0...i3n-1 as base-3 notation of the number i=i0+3i1+32i2+... +33n-1i3n-1, and respectively denote the coefficients of MT by c0,...,c33n-1.

Let cT denote the number of proper colorings of the edges of the triangulation T; we consider colourings as mappings from edges into a 3-element set, so our counting for the triangulation T2 consisting of just 2 triangles gives cT2=6 rather that cT2=1.

It turned out that there are several surprising relations between cT and c0,...,c33n-1.

THEOREM 1. cT=27-n SUMk=0..33n-1ck2.
COROLLARY 2. 4CC is equivalent to the existence of a non-zero coefficient cm for every triangulation.

It is easy to see from the definition of ck that the sum of all of them is equal to 0 and hence they cannot be all of the same sign. Thus we have

COROLLARY 3a. The 4CC is equivalent to the statement that for every triangulation


COROLLARY 3b. The 4CC is equivalent to the statement that for every triangulation


In fact, the maximum and minimum in the above two corollaries have direct relations with cT:

THEOREM 4a. cT = max{c0,...,c33n-1}.

THEOREM 4b. cT = -2min{c0,...,c33n-1}.

We can also pinpoint a coefficient on which the max in Theorem 4a is reached:

THEOREM 5. cT=c0.

According to Corollary 2, in order to prove the 4CC is sufficient to prove the existence of a coefficient which is non-zero modulo some prime number p. What primes can be used?

THEOREM 6. For every k, ck=0(mod 3).

Theorem 6 says that p=3 cannot be used for finding a non-zero coefficient.
Theorem 7 says that any other module can be used:

THEOREM 7. If cT>0 (which follows from the Four Colour Theorem) and p is a prime different from 3, then there is an index m such that cm is non-zero modulo p.

More theorems can be proved about coefficients ak and bk introduced in the following way. Let us expand the polynomial Sk as

xpk2 xrk +xqk2 xpk +xrk2 xqk- xpk2 xqk -xqk2 xrk -xrk2 xpk.

Then the polynomial NT, and hence the polynomial MT as well, can be formally expanded as the sums of 62n monomials with coefficients equal to either +1 or -1. Let us collect together those monomials of MT which are equal completely, i.e. including the signs too. The resulting coefficients will be denoted ak and bk. For the sake of simplicity of the statements of theorems, we will use different notation depending on the parity of n. Namely, ak (respectively, bk) denotes the number of monomials with coefficient (-1)n (respectively, -(-1)n). In other words,


In the new notation Corollary 2 says that the 4CC is equivalent to the statement that the coefficients ak and bk are not identical. Moreover, it turned out that their square means should be different too, and again we have a precise expression for cT:

THEOREM 8. cT=(-9)-n SUMk=0..33n-1(ak2 -bk2).

According to Corollary 2, in order to prove the 4CC it is sufficient to find an index m such that am and bm are different modulo some prime p, and according to Theorem 5 any prime but 3 can be used. More detailed information is known for p=2.

THEOREM 9. For all k, bk is even.
COROLLARY 10. The 4CC is equivalent to the existence of an odd am for every triangulation.

Each of the 63n monomials with coefficients +1 or -1 in the above described expansion of the polynomial MT has its own history consisting in particular choice of one of the 6 terms in each polynomial Sk. Theorem 9 implies that on the histories one can define a symmetric relation of duality in such a way that:

In terms of such a relation of duality the 4CC conjecture is equivalent to the existence of self-dual histories. Unfortunately, my proof of Theorem 9 is a computational one and does not produce a combinatorial definition of such duality. Nevertheless, I believe that there exist a natural combinatorial definition of duality of histories which has the above listed properties and for which it will be possible to give a direct proof of the existence of self-dual histories, thus giving a new proof of the Four Colour Theorem.

Similar results can be obtained if we formally expand Sk into the sum of 8 terms and respectively expand NT and MT into the sums of 82n monomials.
Corollary 2 was first obtained as an application of my general criterion of colourability of vertices of arbitrary (i.e., not necessary planar) graphs in any number of colours published in A criterion of colorability of vertices of a graph stated in term of edge orientations (in Russian), Discrete analysis (Novosibirsk), Vol. 26 (1974), pp. 65-71.

Other relations between ak, bk, ck and cT were found later and were stated as Problem 21 in "Combinatorial and Asymptotical Analisys", issue 2, G.P.Egorychev (editor), Krasnoyarskii State University, Krasnoyarsk, 1977, pp. 178-179.

More results of this type were proved later by Dmitrii Karpov.

The paper was first put on WWW on July 4, 1997.
URL of my original Home page is http://logic.pdmi.ras.ru/~yumat/index.html.
It has a mirror at http://www.informatik.uni-stuttgart.de/ifi/ti/personen/Matiyasevich/index.html.
All comments can be e-mailed to me, Yuri Matiyasevich.