Maths is just colouring-in, really!

Well, blog posts are just like buses, it seems - you wait ages for one, and then when they do come, they're a bit disappointing and rushed!  Wait, no, hang on...

Today, I want to talk to you about some maths.  Specifically, a branch called Graph Theory, which was the module that kept me sanest during my final year at Uni, primarily because it involved a lot of drawing pretty pictures (a fact which all my geographer friends were quick to take advantage of!).

In Graph Theory, a graph isn't something like this:

it's more like this:

A "graph" in graph theory terms is a collection of points (or "vertices") joined by lines (or "edges").  Graph theorists study various properties of graphs - the minimum number of edges that must be crossed to get between two vertices, the average number of edges meeting at vertices, and so on.  Since these graphs can provide very good models for road layouts and computer networks, you can see how the ability to concisely gather information about them could be useful - but, mostly, we just do it 'cos they're pretty (both mathematically and visually!)

I'm going to talk about something called a Ramsey number, and outline a simple but elegant proof.  This is something where you can follow along at home, kids!  Grab a pen and paper and meet me back here!  Actually, better make that at least two pens (of different colours), though three would be even more helpful.

Got 'em?  Good.

Right, first of all, draw yourself a hexagon - that's a six-sided regular shape, that looks like this:

(Do your best to make the corners sharply defined, rather than curves - it'll make your life easier later on.)

Congratulations, you've drawn your first graph!  Technically, this called C₆, (the C stands for "cyclic", since, as you can see, it resembles a circle in that you can go round in turn and return to your starting place) and there are various things that we could learn from examining it, but I have more a more interesting result in my sights.

Now join each vertex to every other vertex with a straight line.  This should end up looking like this (where the vertices have been highlighted in blue):

What you have drawn is called the "complete graph on 6 vertices", or K₆ for short.  For any number n, K_n is simply n vertices with each one joined to every other. K₁ is just a single vertex, K₂ is a line joining two vertices, K₃ is a triangle, K₄ is a square with the diagonals filled in, and so on, as shown below:

Now, to introduce the Ramsey numbers, I first have to introduce the notion of graph colouring.  This is just as it sounds - a colouration of a graph is a drawing of it where all of the edges have a particular colour.  So, for instance, this is a colouring in red, blue, and green, on an (incomplete) graph of 20 vertices;

and this is a colouring in 7 colours (we would say a "7-colouring") of K₈

(Note that it doesn't matter that the vertices of this graph aren't arranged around the points of an octagon - graph theory only cares about the connectedness (or unconnectedness) of points, not their relative positions.  K₃ is still K₃ whether it's represented as a small scalene triangle, or an equilateral triangle the size of the galaxy)

Now (and don't worry, I'll come back and explain this later), we define the Ramsey number R(m) as being the smallest number n such that, for any 2-colouring of K_m, there will always be a monochromatic K_n.

Phew...what on earth does that mean!  Well, let's start off with a simple example.  Let's try to find R(2) - that is, the smallest number n such that, if we link up all n vertices with either red or blue lines, we'll either have a red K₂ or we'll have a blue K₂.  Well, since K₂ is just a single edge, if there's more than one vertex in our graph, there's bound to be either a red or a blue K₂, otherwise we haven't coloured it all - but if there's only one vertex in our graph, there are no edges (nothing to link to!), so no K₂.  So R(2) is 2.

Let's get a bit more adventurous.  What's R(3)?  Well, it's clearly bigger than 3 - as long as you don't use the same colour to draw all three sides of the triangle, you won't end up with a monochromatic triangle in your colouration.  Similarly, we can 2-colour K4 (remember, a square with the diagonals drawn in) without making a mono-K3 - for instance, draw the outside square in red and the diagonals in blue.

This post is dragging on a little, so I'll set you a question to ponder and give the answer (and proof) in the next post - what is R(3)?  If you think you know it, try to consider how you'd prove it - how can you prove, for instance, that there isn't a satisfactory 2-colouring on a smaller complete graph?  I'll warn you now, while sketching out some ideas will help, trying to prove a result by exhausting all possible colourations will take you a while - there are, for instance, 378 possible colourations of K₈*, so you'll be there for a while!  I'll give the solution and proof next time.

* - where xCy is the choose function, there are 8C2 = 28 edges (for each of the eight vertices, there is precisely one edge for every way of choosing two of them), and so, since there is one colouration for every way of choosing a colour for each of these, there are 28C2 = 378 colourations.  For mathematicians - yes, I'm aware that I've double-counted isomorphic colourations, but if you're seeking a solution by brute force exhaustion like this, it's appropriate to warn of an appropriate upper bound!

EDIT: I tried to get a definitive answer on the number of 2-colourings of K₈ by using Wolfram Alpha, a "computational knowledge engine".  The results were...less than satisfactory: