Ramsey Theory on QI

QI, the popular BBC television programme hosted by Stephen Fry, featured a bit on Ramsey Theory. I’ve recorded the section and put it on to YouTube, although I am afraid the quality is pretty poor:

The question is:

Consider an n-dimensional hypercube and connect each pair of vertices to create a complete graph of 2-to-the-power-n vertices. Colour each of the edges of this graph using only the colours red and black. My question is: What is the smallest value of n for which every colouring necessarily contains a single coloured complete subgraph of four vertices which lie in a plane.

Now this is a question of Ramsey theory, with an additional constraint (that is lies in a plane). For a very basic introduction, see my previous post on the subject.

The problem is famous because an upper bound for the solution is called Graham’s Number, and is usually remarked as the largest number ever seriously used in a mathematics. (This may not in fact be the case anymore however it is not always easy how to compare massive numbers!)

The number is contained from iterating a special case of the Ackermann Function, a function famous in logic and computing for growing very quickly. (It is an example of a computable function which cannot be defined just using (primitive) recursion).

Actually, things like this appear quite often in Ramsey Theory, as the existence proofs often come down to a double-induction. Graham’s Number at least showed it that the problem had a solution, and better bounds were actually found shortly afterwards.

By the way, the Irish bloke on there is Dara O Briain, the comedian and Arsenal fan who was mentioned in a recent post. Actually, he also has a degree in Physics and Mathematics, so he probably understands more than he makes out in this clip!

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

%d bloggers like this: