Map colouring and Gröbner Bases

Posted on May 23, 2015 by admin

This picture is a property of mathscareers.org.uk, who kindly granted permission to use it in this work.

Originating author is Marcelo Escudeiro Hernandes.
By the famous “Four Colour Theorem”, only four colours we need to colour a map so that no bordering regions have the same colour. Using polynomial equations and Gröbner bases we can determine if three colours are sufficient for a particular map.

1. Map Colouring
The celebrated Four Colours Theorem (1) states that all maps, whether in a plane or sphere, can be coloured with four colours without neighbouring regions being the same colour. It is very easy to produce examples of maps that cannot be coloured with three colours and others that can. A way to decide if three colours are sufficient to colour one particular map, is to analyse a polynomial system associated to the map. Each colour is represented by a complex cubic root of the unit and each region by a variable x_i such that it can assume only one of three values, that is, one of the three colours. Thus, we have {x_i}^3 - 1 = 0 for each region.

For regions x_j and x_k , we have 0= x_j ^3 -x_k ^3 =(x_j -x_k)(x_j ^2 +x_j x_k + x_k ^2). If x_j and x_k are neighbouring regions, and as neighbouring regions cannot have the same colour, then x_j \neq x_k, that is, x_j ^2+ x_j x_k + x_k ^2=0. In this way, a map with n regions can be colored with three colours if, and only if, the system of polynomial equations

(1)   \begin{eqnarray*} \left\{ \begin{array}{l} x_i ^3-1=0 ~,\\ x_j ^2+ x_j x_k + x_k ^2=0 ~, \end{array}\right. \end{eqnarray*}

where i= 1 , ... , n and x_j and x_k represent adjacent regions, has at least one solution.

Example 1.

We consider the map:

Figure 1.

Can it be colored with three colours?

To answer this question we must verify that the polynomial system 1 with i = 1, ..., 9 and


Rendered by QuickLaTeX.com

can be solved.

2. Systems of polynomial equations

The answer of many problems in mathematics is due to the solution of systems of polynomial equations, which is not always easy. If the system is given by linear equations, we can, through Gaussian elimination, substitute the system for another equivalent whose solution is simpler. In the case of polynomial systems, it has an analogous method that we describe below.

We will denote by P(n) the set of polynomials with complex coefficients with variables x_1 , ... , x_n. Given a set of polynomials f_1, ... , f_r in P(n), we determine the ideal generated for them as being

    \[I = \langle f_1, ... , f_r \rangle = \{ h_1 f_1 + ... + h_r f_r \mid h_1 , ... , h_r \in P(n) \}.\]

A theorem due to the mathematician David Hilbert <http://www.mat.uniroma1.it/people/manetti/dispense/nullstellen.pdf”>(2), called Hilbert’s Nullstellensatz, states that the system f_1 = ... = f_r = 0 admits a (complex) solution if and only if 1 \notin \langle f_1 , ... , f_r \rangle. But how can we check the last condition?

It is very simple to verify that two systems of equations f_1 = ... = f_r = 0 and g_1 = ... = g_s = 0, where f_i, g_j \in P (n), satisfying the condition

(2)   \begin{eqnarray*} \langle f_1 , ... , f_r \rangle = \langle g_1 , ... , g_r \rangle , \end{eqnarray*}

have the same solution.

Therefore, the strategy to solve a system f_1 = ... = f_r = 0 consists to find polynomials g_1, ... , g_s which satisfy the condition 2 and with which it is possible to test if a given f \in P (n) belongs or not to the ideal \langle f_1, ... , f_r \rangle and whose common solution is easier to compute than the original system.

The existence of such G = \{ g_1 , ... , g_s \} was discovered theoretically during the first half of the last century by the mathematician Wolfgang Gröbner. Some years later, his student Bruno Buchberger created an algorithm to compute it. These sets are called Gröbner bases and Buchberger’s algorithm to compute them is one of the most important tools of algebraic computation.

If the ideal is of the form I = \langle f_1 \rangle, we have f \in I if and only if f = h_1 f_1, that is, f is divisible by f_1. Analogously, f \in \langle f_1 , ... , f_r \rangle if and only if f = h_1 f_1 + ... + h_r f_r, which suggests something similar for the division of f by f_1 , ... , f_r. In fact, we can divide a polynomial in several variables by a finite set of polynomials, provided that the monomials are ordered in some way.

3. Gröbner Bases

A monomial m of P (n) is an element of the form x_1 ^{a_1} ... x_n ^{a_n}, where a_1 , ... , a_n non-negative integers. The monomial x_1 ^0 ... x_n ^0 will be denoted by 1. Among the orders \preceq on the monomials of P (n), the ones that satisfy 1 \preceq m and m_1 .m \preceq m_2 .m whenever m_1 \preceq m_2 are the ones which make it possible to put into practice the algorithm of the division.

An example is the lexicographical order \preceq_{Lex}, where x_1 ^{a_1} ... x_n ^{a_n} \preceq_{Lex} x_1 ^{b_1} ... x_n ^{b_n}, if there exists 1 \leqslant i \leqslant n such that a_i < b_i and a_j = b_j for all j < i.

Fixed an order on the monomials, the greatest monomial of a polynomial f it is called the leading term of f and denoted by lt (f).

A Gröbner basis of an ideal I = \langle f_1 , ... , f_r\rangle with respect to a given monomial order, is, by definition, any set G = \{ g_1 , ... , g_s \} of elements of I such that the leading term of any element of I is divisible by the leading term of some element of G. We can show that any Gröbner basis G of I is a set that satisfies the condition 2.

Therefore, 1 \in I if and only if there exists a Gröbner basis of I containing a non-zero constant, since 1 \preceq m, for all monomial m of P (n).

For example, G = \{ f_1 \} is a Gröbner basis of \langle f_1 \rangle, with respect to any monomial order, whereas G = \{ x+y+z-6, x-y+1, x+y-z \} is not a Gröbner basis of I = \langle x+y+z-6, x-y+1, x+y-z \rangle with respect to the lexicographical order, because lt(x+y+z-6-(x-y+1)) = lt(2y+z-7) = 2y is not divisible by x = lt(x + y + z - 6) = lt(x - y + 1) = lt(x + y - z).

To get a Gröbner basis of an ideal, with respect to a chosen monomial order, you can apply Buchberger’s algorithm (3). We find algorithms to calculate Gröbner bases in a majority of computer algebra systems.

For instance, a Gröbner basis for the ideal I = \langle x+y+z-6, x-y+1, x+y-z \rangle, with respect to the lexicographical order is G = \{ x+y +z -6, 2y +z -7, 2z -6 \}.

4. Solution of the problem and other applications

The system given in Example 1, has at most a finite number of solutions (nine variables, each of them being able to take one of three values). The problem is to determine if the system admits any solution, and in that case, to determine it.

Applying Buchberger’s algorithm to the system of Example 1, we get the following Gröbner basis G, with respect to the lexicographical order:


Rendered by QuickLaTeX.com

Therefore, 1 \notin I and,consequently, the system admits solutions. The equations

    \[\left\{ \begin{array}{l} x_1 ^3 - 1 = 0 ~,\\ x_2 ^2 + x_2 x_1 + x_1 ^2 = 0 ~,\\ x_5 - x_2 = 0 ~,\\ x_7 - x_2 = 0 ~,\\ x_9 -x_3 = 0 ~, \end{array}\right.\]

translate the following fact: we can use any colour for x_1, x_2 \neq x_1, x_2 = x_5 = x_7 and x_3 = x_9.

As the colours are represented by the complex cubical roots of the unit, the only solution for x_4 + x_3 + x_2 = 0, x_6 + x_3 + x_2 = 0 and x_8 + x_3 + x_2 = 0 is to attribute values (colours) distinct for x_2, x_3 and x_4, and thus, x_4 = x_6 = x_8. Finally, 0 = x_3 ^2 + x_3 x_2 -x_2 x_1 -x_1 ^2 = (x_3 + x_2 + x_1 )(x_3 - x_1 ) gives us two
possibilities: x_3 +x_2 +x_1 = 0 or x_3 -x_1 = 0, that is, x_1, x_2 and x_3 take distinct colours or x_1 = x_3. And thus, we find, up to permutations of the colours, all the possible solutions:

Figure 2.

Gröbner bases also can be used to operate with ideals, converting parametric equations to their implicit equations (some surfaces and curves for examples) into nonparametric equations, to compute the minimum polynomial of algebraic numbers, to verify theorems of Euclidean Geometry, to validate constructions with Origami and to solve Sudoku puzzles (See (4), (5) and (6)).

References

(1) http://www.ipv.pt/millenium/Millenium24/12.pdf

(2) http://www.mat.uniroma1.it/people/manetti/dispense/nullstellen.pdf

(3) https://www.risc.jku.at/people/buchberg/papers/1970-00-00-A.english.pdf

(4) Adams, W. and Loustaunau, P., An Introduction to Gröbner Basis, AMS, Providence RI (1994).

(5) Cox, D; Little, J. and O’Shea, D., Ideals, Varieties and Algorithms, 2nd edition, Springer-Verlag, New York, (1996).

(6) Hernandes, M. E., Um Primeiro Contato com Bases de Gröbner, 28°. Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro, (2011).

This entry was posted in Mathematics Within the Last 100 Years. Bookmark the permalink.

3 Responses to Map colouring and Gröbner Bases

  1. Anonymous says:
    November 26, 2012 at 3:23 am

    Are ordinary senior secondary teachers supposed to be able to understand this?

    This article is not in keeping with the Klein blog. It’s way way too difficult to follow along. I was excited about the complex numbers connection but I’d need to be a trained university lecturer to make sense of this…

    Reply
    • Antoine Nectoux says:
      November 26, 2012 at 3:27 am

      It is not that hard… You only need to have some knowledge in ideals and rings to understand it, and these notions are taught in 3rd year of university. Some vignettes require a little effort !

      Reply
  2. David Fowler says:
    October 2, 2015 at 4:38 am

    I think for secondary teachers to struggle with an article like this. It helps them get some insights into the world beyond “precalc”, etc.

    Would be useful to have an accompanying reference on “Groebner for Beginners” to help with some examples.

    Michael Trott, at Wolfram Research, wrote some interesting articles on solving problems with Groebner bases. Mathematica is more universal now than it used to be, and these might also be helpful.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *