The Chromatic Number of the Plane

To introduce the problem in the title, we begin with a quotation from the Foreword, written by Branko Grünbaum, to the book by Alexander Soifer (2009): The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators:

If each point of the plane is to be given a color, how many colors do we need if every two points at unit distance are to receive distinct colors?

About 70 years ago it was shown that the least number of colours needed for such a colouring is one of 4, 5, 6 and 7. But which of these is the correct number? Despite efforts by many very clever people, some of whom had solved problems that appeared to be much harder, no advance has been made to narrow the gap

${4\le\chi\le 7}$ .

Colourng Graphs

A graph is a set ${\mathcal{V}}$ of points, called vertices, and a set ${\mathcal{E}}$ of links, or edges, between them. Two vertices ${v_1, v_2\in \mathcal V}$ are adjacent if they are joined by a link. We can divide the set ${\mathcal{V}}$ into subsets

$\displaystyle \mathcal{V} = \mathcal{V}_1 \cup \mathcal{V}_2 \cup \cdots \cup \mathcal{V}_n$

and identify elements by assigning a colour to each subset. This assignment is a colouring of the graph ${G = (\mathcal{V},\mathcal{E})}$ , if no two adjacent points have the same colour. Thus, for a coloured graph, no two elements of any ${\mathcal{V}_k}$ are linked by an edge. The minimum number of colours needed to ensure this is called the chromatic number of the graph, and is denoted as ${\chi{(G)}}$ .

The legendary Four-Colour Theorem is an example of a graph-colouring problem. We place a vertex in each region or country and link two vertices if the corresponding two countries share a border. The theorem states that the chromatic number of the graph of any planar map is never greater than 4.

Estabishing the range for ${\chi}$

The Euclidean plane ${\mathbb{R}^2}$ may be regarded as an infinite graph. We will assume an edge between every pair of points that are a unit distance from each other. The problem of the chromatic number of the plane may thus be stated: What is the smallest number of colours sufficient for colouring the plane in such a way that no two points of the same colour are a unit distance apart? The chromatic number of the plane is denoted by ${\chi(\mathbb{R}^2)}$ , or simply ${\chi}$ .

Anyone can understand this problem; it asks for the chromatic number of the infinite graph whose vertices are all the points in the plane and whose edges are all pairs of points at unit distance. Yet, despite its apparent simplicity, no one has been able to answer it during the 70 years since it has been formulated.

Left: “Moser’s Scissors” open. Right: “Moser’s Scissors” closed.

It is trivial to show that ${\chi \ge 3}$ . Just consider any equilateral triangle in the plane with unit length sides. We can eaaily do better than this. A clever graph known as the Moser Spindle, was discovered by Leo Moser. Consider two rhombi, each made of two equilateral triangles, sharing a common vertex (Figure above, left panel). Now, keeping them rigid, rotate the rhombi about the top point until the lowest points are a unit distance apart, and add an edge between these points. (Figure above, right panel). Then it is clear that these two points must be assigned different colours. But that implies that four colours are required.

Tiling in hexagons with ${\chi = 7}$ [figure based on Soifer (2009)].

It is easy to find a tiling of the plane using hexagons of the right size that can then be coloured with seven colours to demonstrate that the chromatic number of the plane is not greater than seven (see Figure above).

The underlying axioms

Alexander Soifer (2009) undertook a careful investigation of the origin of the problem and gave credit to American mathematician Edward Nelson for being the first person to formulate the problem (in 1950) and to prove the lower bound ${4 \le \chi}$ . Because of this bound, Nelson liked to call it a “second four-colour problem”. Around the same time, the problem was studied by a Swiss mathematician, Hugo Hadwiger and it is often called the Hadwiger-Nelson Problem. But we will stick with describing the problem as the Chromatic Number of the Plane. In his book (2009), Soifer conjectured that ${\chi = 7}$ .

Soifer suggests that the solution of the problem may depend on the axiom system. By considering axiom systems other than the standard ZFC, Shelah and Soifer (2003) constructed a graph whose chromatic number is 2 in ZFC, but is uncountable in an axiom system where the axiom of choice is replaced by an axiom saying that every set of real numbers is Lebesgue measurable.

Joseph Edward Nelson (1932-2014)

Joseph Edward Nelson was born in 1932 near Atlanta, Georgia. In 1949 he entered the University of Chicago. Nelson’s exceptional abilities were quickly recognised, and he was allowed to go straight to graduate school without obtaining a bachelor’s degree. Having obtaining a doctorate from the University of Chicago in 1955, Nelson became a Postdoctoral Fellow at the Institute for Advanced Study in Princeton. Three years later he became a professor at Princeton University, where he remained for the rest of his career. Nelson was elected to the American Academy of Arts and Sciences, and to the National Academy of Sciences.

Sources

${\bullet}$ Saharon Shelah and Alexander Soifer, 2003: Axiom of choice and chromatic number of the plane. J. Combin. Theory, Series A, 103, 387-391.

${\bullet}$ Soifer, Alexander, 2009: The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. Springer, New York. xxx+607 pp. ISBN 978-0-387-74640-1.

${\bullet}$ Wikipedia article Hadwiger-Nelson problem: http://www.wikipedia.org/

* * *

BARGAIN BASEMENT

New Collection just Published

HALF-PRICE THIS MONTH from Logic Press

ThatsMaths