A Polynomial related to Colourings of Triangulation of Sphere

This HTML paper is written especially for

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

With every triangulation *T* of a sphere we associate a polynomial
*M _{T}* in many variables, coefficients of which are related
in several unexpected ways to the number

Let *T* be a triangulation of a sphere with *2n* triangles.
Such a triangulation has *3n* edges which will be denoted *e _{0}*,...,

Let us associate with each edge *e _{i}* of the triangulation
a formal variable

*(e _{pk} -e_{qk}) (e_{qk} -e_{rk})
(e_{rk} -e_{pk}). *

Let *N _{T}* denote the (auxiliary) polynomial equal to
the product of all

The polynomial *M _{T}* is the sum of

*c _{i0...i3n-1} x_{0}^{i0}...
x_{3n-1}^{i3n-1}. *

To simplify notation, we will view the multiindex *i _{0}...i_{3n-1}*
as base-3 notation of the number

Let *c _{T}* denote the number of proper colorings of the
edges of the triangulation

It turned out that there are several surprising relations between *c _{T}*
and

THEOREM 1.

COROLLARY 2. 4CC is equivalent to the existence of a non-zero coefficient

It is easy to see from the definition of *c _{k}* 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

max{*c _{0},...,c_{33n-1}*}>0.

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

min{*c _{0},...,c_{33n-1}*}<0.

In fact, the maximum and minimum in the above two corollaries have direct
relations with *c _{T}*:

THEOREM 4a.

THEOREM 4b. *c _{T}* = -2min{

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

THEOREM 5.

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

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

More theorems can be proved about coefficients *a _{k}*
and

*x _{pk}^{2} x_{rk} +x_{qk}^{2}
x_{pk} +x_{rk}^{2} x_{qk}- x_{pk}^{2}
x_{qk} -x_{qk}^{2} x_{rk} -x_{rk}^{2}
x_{pk}*.

Then the polynomial *N _{T}*, and hence the polynomial

*c _{k}*=(-1)

In the new notation Corollary 2 says that the 4CC is equivalent to the
statement that the coefficients *a _{k}* and

THEOREM 8.

According to Corollary 2, in order to prove the 4CC it is sufficient
to find an index *m* such that *a _{m}* and

THEOREM 9. For all

COROLLARY 10. The 4CC is equivalent to the existence of an odd

Each of the 6* ^{3n}* monomials with coefficients +1 or
-1 in the above described expansion of the polynomial

- terms with dual histories are equal;
- for each history there is exactly one dual history;
- histories corresponding to monomials with coefficients
*-(-1)*are not self-dual;^{n} - different self-dual histories correspond to different monomials.

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

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

Other relations between *a _{k}*,

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.