Some comments on colouring

A friend of mine posted a neat colouring problem to stack.exchange this week that implicitly contained the fact that any graph embedded on a sphere can be 4-coloured, which follows from the fact that a graph is planar iff it can be embedded on a sphere. This follows immediately from sensible stereographic projection, but it raises the more interesting question of how colourings behave for graphs embedded on more general surfaces. Perhaps there’s my interest in dimer models ticking away subconsciously too…

It turns out that there is a beautifully uniform treatment of the chromatic number for even not necessarily orientable surfaces due to Ringel and Youngs in the 1960s, completing work of Heawood in the 1890s. Sadly, Heawood believed that he had proved the strong version that the other two authors later corrected using more sophisticated techniques. This is also an instance of a single exceptionally tricky case of a problem resisting proof, since Ringel and Youngs prove Heawood’s conjecture for all surfaces apart from the sphere (or the plane), which was the subject of the four colour theorem proved a decade later.

I say ‘an instance’ as this is quite analogous to the Poincaré conjecture, where it was proved that a [topological] n-manifold homotopic to a n-sphere is actually homeomorphic to the sphere when n\geq 5 by Smale also in the 1960s. There’s an amusing and slightly sorrowful anecdote I was told during my time at Warwick about the late Sir Christopher Zeeman who proved the Poincaré conjecture in dimension 5 shortly before Smale obliterated the problem in all dimensions except 3 and 4. Freedman proved the conjecture in dimension 4 in 1982, before Perelman’s proof for dimension 3 in the early 2000s.

This area also exhibits pleasing applications of logic to everyday mathematical problems: one can extend colouring theorems such as these from finite graphs to infinite graphs immediately by appealing to Gödel’s compactness theorem. Here are my notes on the proof of Heawood’s conjecture for nonspheres, which should be moderately accessible to nonmathematicians who care more about my poetry!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s