A little more colouring-in

(This is a follow-up post to this one, where I introduced you to the wonderful world of Graph Theory)



So, I trust you've all been waiting with bated breath for the answer to the riddle ("What is R(3)?") I set at the end of last post?  Of course you have been.

Well, as you've probably guessed from the fact that I started the post by introducing K₆, the answer is 6.  That is, R(3) = 6 - or, more wordily, for any 2-colouring of K₆, there will be a monochromatic K₃, but there exist 2-colourings of K5, that do not contain a monochromatic K₃.


There are two parts to this statement - "for any 2-colouring of K₆, there will be a monochromatic K₃", and "there exist 2-colourings of K5, that do not contain a monochromatic K₃".  We'll prove them in reverse order, using different mathematical methods of proof for each.

The second statement is the simplest to proof.  We can use a technique known as proof by exhibition, which basically consists of describing the object you're looking for, pointing at it, and going "look, there it is!".  In this case, we seek a 2-colouring of K5 that contains no mono K3.  The following is a rather visually pleasing example, which has however garnered some unfortunate associations that are beyond the scope of this blog:

The first statement requires us to prove that any 2-colouring of K5 will always contain a mono K3. If we were to attempt to prove this by exhibition (or, as it would pejoratively be called in this case, by brute force), we would draw every possible 2-colouring (rather time-consuming!), prove that we'd drawn all of them (which is non-trivial unless you've done some study on combinatorics - although you should, because, being the study of counting, it ties with graph theory as the discipline with the most self-deprecating description!), show that none of them contain a mono K3, then (probably) shrug and feel a little bit like we've wasted our time.

The elegant way to prove is as follows (it will be immeasurably helpful if you have drawn out a copy of K6 that you can colour over the top of here - see last post for a guide!):

1. Pick a vertex.  Call it x. Well, you can call it anything, you can call it Nancy if you like, but I'm going to call it x because mathematicians like x (maybe because we don't get enough of that thing that sounds like it?)
2. There are 6 vertices in our graph, so there are 5 vertices linked to x/Nancy, and so 5 edges coming out of it.  If we're using Red/Blue to colour the edges (and, again, you can choose any two colours you like - Yellow/Green, Fuchsia/Aquamarine, Onion/Wistfulness - it's up to you), there are 5 possible colour combinations:
• 0 Blue, 5 Red
• 1 Blue, 4 Red
• 2 Blue, 3 Red
• 3 Blue, 2 Red
• 4 Blue, 1 Red
• 5 Blue, 0 Red
3. Note that, in all of these cases, there is (at least) one colour that has more than three edges linked to x. So, whatever the colouring is, we will be able to find a group of at least 3 vertices that are linked to another vertex by edges of the same colour.  That is, we have a case like this: 
   
   
   where the colours of the grey edges are, as yet, undetermined (note that I've chosen red as our "at least 3" colour here - if one were to end up with a colouring in which there were 2 or fewer red edges, then there would be 3 or more blue edges, so one could reverse the words "red" and "blue" from here on in, and still arrive at a proof)
4. Consider the set of vertices linked to x by red edges.  We know there are at least three of them.  Pick three vertices from the set. There are three edges between these three vertices.  We must now consider two possibilities:
1. All three edges are blue, or 
2. At least one of the edges is red.
5. If all three edges are blue, then we have a blue triangle, and the specific case of the original statement ( "for [this] 2-colouring of K₆, there will be a monochromatic K₃" ) is satisfied. But if at least one of the edges is red, then it forms a red triangle with the two red edges from its edges to x - so the statement is once again satisfied, and so is satisfied in all cases. Q.E.D. (bitches)

Phew - did you get through all of that!  Though it may have been tough going in some cases, I can guarantee you that it was quicker than drawing out all the colourings by hand!

What's more, though you may not have noticed it at the time, you learnt something by doing it this way that you wouldn't have done if you'd "proved" it by hand (in fact, there's a strong feeling in mathematics that a proof isn't really worth anything if you don't learn something from it).  Did you notice how the proof rested on the fact that, in a set of three completely connected vertices, if there wasn't a triangle of one colour then there would be at least one edge of the other colour?  This is related to an expanded view of Ramsey numbers, taking two arguments - i.e. R(n, m) is the smallest number such that K_{R(n, m)} will always contain either a mono-K_n or a mono-K_m. (Note that R(n) is equal to R(n, n)...mull it over for a while and it should click into place!) A crude method of approximating the higher Ramsey numbers involves repeating the method above (picking a vertex, looking at the smallest possible group of vertices joined to it by edges of a single colour, and applying knowledge about lower Ramsey numbers), though of course there are more accurate methods.

I'll leave you with two amusing (at least, I think they're amusing!) examples of how mind-blowingly large the possible number of examples of graphs to be considered can get.  Quoting from Wikipedia, itself quoting Joel Spencer, himself quoting Erdős, one of the most prodigious and eccentric mathematicians of recent years :

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.

The second example is a number known as Graham's number.  Graham's number (henceforth represented by G) is the upper bound for the answer to a question in Ramsey Theory - that is, we do not know the answer to the question, but we know that it is smaller than G.  G is large. Very large. It is larger than a million, or a googol (the digit 1 followed by 100 zeroes - the inspiration for the name Google). It is larger than a googolplex (1 followed by a googol zeroes). It is, in fact, so large that, even if every atom in the universe were converted into ink (and we found a giant piece of paper from one of those handy parallel universes), that still wouldn't be enough ink to write it out (or, for the physicists among you, it is larger than the number of Planck volumes in the universe).  It is well big, 'innit.

The amusing part of the story?  I said that G was the upper bound for the answer to a question, as in the answer is bigger than some other number but smaller than G.  Our best guess for the lower bound is currently 6.  Not the best precision on that answer.