Colouring in like a mathematician

BLOG: Heidelberg Laureate Forum

Laureates of mathematics and computer science meet the next generation
Heidelberg Laureate Forum

A recent mathematical breakthrough has been made, in the area of… colouring in. No, really! A recent proof by scientist Aubrey de Grey has improved on a long-standing result about the chromatic number of the 2-dimensional plane, and colouring in will never be quite the same again.

Colouring problems

Four regions to be coloured, and the associated graph
Four regions to be coloured, and the associated graph

One very famous result in the mathematics of colouring problems is the Four Colour Theorem. This states that for any diagram you can draw on a piece of paper, the maximum number of colours you’ll ever need to colour it in, so that any two regions which share an edge are different colours, is four. This means that on a flat surface like a piece of paper, it’s not possible to draw a diagram which needs more than four colours. Go on, try it now. You can’t do it.

This result was proved in the 1970s, and the mathematics underlying the proof is graph theory. Graphs are collections of points joined in a network, with lines between some (but not necessarily all) of the pairs of points, called nodes. In the case of a colouring problem, the shape and size of the regions you’re colouring is unimportant, and the only crucial fact is the way the pieces connect together – which is captured by the structure of the graph, if each node represents one region which needs colouring.

Colouring a graph is as simple as assigning a colour to each node, so that any pair of nodes which are connected use different colours. Colourability (or otherwise) of a graph is often a useful property of the graph to know, and it’s been well studied. If a graph can be coloured with three colours, it’s called three-colourable.

The mathematics that’s been of interest recently, however, doesn’t just involve colouring separate nodes in a network – but every single point of an infinite plane.

Chromaticity

Colouring of a tessellation of hexagons using 7 colours - each hexagon is surrounded by a layer of hexagons two thick that don't share its colour
Grid of hexagons; proof attributed to John Isbell

The Hadwiger-Nelson problem asks the following question: what’s the minimum number of colours required to colour every single point on the 2-dimensional plane, so that no two points that are exactly one unit of distance apart are the same colour? The answer to this question is called the chromatic number of the plane, and we, um, still don’t actually know exactly what it is.

We’ve known for a while that the maximum number of colours you might need to colour the plane in this way is 7, and we know this because of a proof attributed to American mathematician John Isbell. If you divide the whole plane up into tessellating hexagons, and colour them in using 7 different colours in the pattern shown in the diagram, this is a colouring of the plane which doesn’t have two points distance 1 apart that are the same colour (assuming the hexagons are slightly less than 1 unit across from point to point).

Since 1961, we’ve also known that the minimum this number can be is 4. This was proved using a construction called the Moser Spindle, discovered by mathematical siblings William and Leo Moser. The shape is shown in the diagrams below, and is made up of two pairs of equilateral triangles stuck back-to-back, with an extra line joining the bottom two points. The lengths of the lines in the figure are all 1 unit, which means in order to colour the plane you’d need to be able to colour all the points in this diagram – in particular, the two points at the end of each line need to be different colours. The claim that this can’t be done using three colours is argued as follows.

If the very top point in the diagram is coloured using colour A, then each of the two bottom corners of a triangle attached to it must be coloured B and C, in some combination. This means the very bottom point of that pair of triangles must be coloured A as well. But this argument follows equally for both of the triangle pairs in the diagram, and so both bottom points must be colour A – which is a problem, as they’re 1 unit apart, and therefore can’t be the same colour.

It’s important to note we’re not just dealing with a normal graph here. The Moser Spindle as a graph can’t be three-coloured however you draw it, because of the way it’s connected up – but in this case it’s crucial that the arcs (lines) making up the graph have specific lengths: the Moser Spindle is a unit-distance graph, meaning all the lengths are 1. This fact makes the property of not being three-colourable extend from being true of the graph to being true of the plane as given in the Hadwiger-Nelson problem.

The nice thing about this problem is that it uses ideas from both graph theory and geometry – measuring distance is part of the problem, but graph theory lends its tools to prove things can’t be coloured in this way.

Chromatic Developments

Although the Hadwiger-Nelson problem was first formulated in 1950, all we’ve really managed to prove is that the number is somewhere between 4 and 7. Until now! In the last month, biomedical scientist and, it turns out, mathematician, Aubrey de Grey has announced a new proof, in which he’s constructed a bigger more complex unit-distance graph, increasing the lower bound on this problem from 4 to 5.

The graph de Grey constructed in his paper, which was released on the online preprint server the ArXiV on 8th April 2018, is constructed from smaller, simpler graphs. In the same way that the Moser Spindle is made from two pairs of rigid equilateral triangles, angled so that the distance between their ends is also 1, de Grey’s graph is made up by layering multiple copies of triangulated hexagons. After several layers of repeats, the final graph has 1581 vertices, and provably can’t be four-coloured. So the minimum must be five.

De Grey’s paper also includes discussion of how computer programs can be used to assemble and verify the colourability of the hugely complex graph. Since the release of the paper, the mathematical community has been buzzing with excitement – and proof checking software known as an SAT solver has been used to check the proof.

The next stage is to see if it’s possible to reduce the size of this monstrous graph, to create a neater proof – I expect we won’t quite get to Moser Spindle levels of elegance, but it’s good to try. Several mathematicians, including de Grey himself, have proposed that a good way to do this might be through a Polymath project. Polymath is an online community of mathematicians, who can all collaborate and work on problems together that can easily be split into smaller tasks, and it’s previously been instrumental in this kind of proof optimisation.

The Polymath project on the Hadwiger-Nelson problem, called Polymath16, aims to find smaller non-four-colourable unit-distance graphs, and also to reduce the extent to which the proof depends on computer checking. It’s already discovered a smaller graph which has the same property, with 826 vertices, which can be seen (well, kind of) in the image below.

 

826-vertex graph, requiring a minimum of 5 colours. Image by Marijn Heule.
826-vertex graph, requiring a minimum of 5 colours. Image by Marijn Heule.

Work on this project continues, and anyone looking for a minimal way to colour in the plane now has a narrower target to aim at. The mathematics and computer code developed in order to solve this problem enriches the theory of graphs and feeds into other mathematics, but it also takes us a step closer to cracking this gorgeous puzzle.

Avatar photo

Posted by

is a mathematician based in Manchester, who gives talks and workshops on different areas of maths. She finished her PhD in 2011, and since then has talked about maths in schools, at science festivals, on BBC radio, at music festivals, as part of theatre shows and on the internet. Katie writes blog posts and editorials for The Aperiodical, a semi-regular maths news site.

1 comment

Leave a Reply


E-Mail-Benachrichtigung bei weiteren Kommentaren.
-- Auch möglich: Abo ohne Kommentar. +