Map colouring and Gröbner Bases

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

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:

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).

3 réponses à Map colouring and Gröbner Bases

Anonymous dit :

novembre 26, 2012 à 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…

Répondre
- Antoine Nectoux dit :
  
  novembre 26, 2012 à 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 !
  
  Répondre
David Fowler dit :

octobre 2, 2015 à 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.

Répondre

Map colouring and Gröbner Bases

Related

3 réponses à Map colouring and Gröbner Bases

Laisser un commentaire Annuler la réponse

Receive notice of every new vignette.

Search

Meta

Map colouring and Gröbner Bases

Partager :

Related

3 réponses à Map colouring and Gröbner Bases

Laisser un commentaire Annuler la réponse

Receive notice of every new vignette.

Search

Meta