By An Ran Chen, Australian National University
In 1852, the South African mathematician and botanist Francis Guthrie asked a seemingly simple question, “Is it possible to colour any map with at most four colours?” – by that he meant giving each region on the map a colour so that no neighbouring regions have the same colour. As is the case with many simply phrased questions in maths, this problem turned out to be so incredibly difficult that it troubled mathematicians for more than a hundred years. Many attempted the problem and many solutions and counterexamples were proclaimed but they all turned out to be false.
This four-colour problem can be studied in terms of the colouring of planar graphs. Let each region on the map be a vertex (think of it as a node or a point), and the relation that the regions are neighbours be an edge (think of it as a line) joining the vertices representing the regions, then each map can be considered as a graph. In particular, all maps are planar i.e. graphs that can be drawn on a piece of paper without having its edges crossing. Now the problem becomes colouring the vertices with at most four colours in a way where any two connected vertices are coloured differently.
In my project, I am studying a function developed by George David Birkhoff in 1912 called the chromatic polynomial. He thought this function might be the solution to the four-colour problem. The function works as follows: given a graph and n-number of colours, it counts the number of ways one can colour the graph using these n colours.
In the first part of my project, I read to understand how exactly the properties of the chromatic polynomial worked. Then I looked at mathematical objects called partially ordered sets that can be derived from a graph. It turned out that we could count the number of colourings of the graph in terms of these partially ordered sets. This gave us extra insight on how the chromatic polynomial works by taking information we already knew about the partially ordered sets and translating it into the language of the chromatic polynomials. This should minimize the effort of separately formulating a system of knowledge of chromatic polynomials and proving statements about them.
Unfortunately, Birkhoff did not prove the four -colour theorem with his chromatic polynomials. These polynomials, however, are still significant and were found to be connected to the area of statistical mechanics in physics and even today, people still study them.
As for the four-colour theorem, it was finally proven in 1976 (124 years after Guthrie asked the question!) by Kenneth Appel and Wolfgang Haken. It involved the calculation of so many cases that they had to use a computer for assistance.
An Ran Chen was one of the recipients of a 2015/16 AMSI Vacation Research Scholarship.