January 14, 2006

Something completely ridiculous and impossible, but true

I haven't done a maths entry for ages, but today I went to an absolutely amazing colloquium at the maths department. Professor Cameron started portentously by saying:

I am about to tell you something that you will find completely ridiculous and impossible, but 5 minutes later you'll be absolutely convinced that it's true, and in fact you'll think it's completely obvious. I think maths is the only academic subject in which this can happen.

For the interested non-mathematicians, I should explain a couple of terms. In this entry, when I say "a graph", think of a collection of dots joined by lines. The dots are called vertices, the lines are called edges. A simple example is a network of roads between towns: each town is a vertex of the graph, and each road joining two towns is an edge between two vertices. Graphs are quite abstract and can be used to represent all sorts of situations. Here is another example of a graph. Imagine a party where some know each other and some don't. This defines a graph, each person is a vertex, and each vertex (person) is joined by an edge if the two people know each other.

Back to the colloqium. The ridiculous and seemingly impossible statement was as follows. Suppose you and I each choose a random infinite graph. That is, we choose a graph with an infinite number of vertices, where for each pair of vertices there is an edge between them with probability 1/2 (and these probabilities are all independent). Another way of putting it is that we build our graph by considering every pair of vertices, and we toss a coin to decide whether or not there should be an edge between these two vertices. The ridiculous statement is that with probability 1, we will choose the same graph.

Seems impossible? Let me explain a bit more. We may need to relabel our vertices. That is my vertex called A may correspond to your vertex called B, but the names we give to the vertices aren't important, it's the way we join them up that is important. With this understood, with probability 1 we have chosen the same graph.

Saying that it happens with probability 1 doesn't mean that it always happens. For example, suppose I chose every pair of vertices to be joined by an edge, and you chose no pair of vertices to be joined by an edge. These graphs are obviously not the same. But, there is a probability of 0 of our choosing these particular two graphs at random, so although it could happen, it will happen with probability 0.

I can even go one stage further and tell you exactly what graph we have both chosen entirely at random. Suppose I label the vertices with the natural numbers 0,1,2,3,..., then in this graph, called the Rado graph, we join x<y with an edge if the xth digit of y written out in base 2 is 1.

Things get even stranger. This graph is universal. That means that every possible infinite graph appears inside a randomly chosen one (with probability 1). What this means is that if you give me any infinite graph (not just the randomly chosen one, but the unlikely ones too), I can find a collection of vertices in my random graph which correspond to your graph, in the sense that if I ignore all the other vertices and all the edges connected to them, what remains will be precisely your graph.

I think this is remarkable: all possible graphs are contained in one particular graph, and not only that but this particular graph is the one you get when you just choose one at random.

So here's how to see that it's true. First of all, a little definition. We say that a graph has property (*) if whenever you choose two finite (disjoint) sets of vertices U and V, there is at least one vertex x in the graph so that x is joined to every vertex in U by an edge, and to no vertex in V. It turns out that random graphs have property (*) with probability 1. It also turns out that any two graphs with property (*) must be the same.

The first step then is to show that random graphs have property (*) with probability 1. The way to do this is to show that they fail to have property (*) with probability 0. So here's how. Suppose you've chosen two sets of vertices U and V, and suppose that there are a total of n vertices in U and V together. Now, I simply choose any vertex x. The chance that x will be joined to everything in U and nothing in V is just (1/2)n because each edge is chosen independently at random with probability 1/2 and there are n possible edges to consider. So the probability of x not being connected to everything in U and nothing in V is 1-(1/2)n which is ever so slightly less than 1. Now choose another vertex and do the same thing. The chance that neither of these two vertices will be joined to everything in U and nothing in V is (1-(1/2)n)2. Keep doing this again and again with the infinite number of vertices you still have to play with and you'll see that the chance of never finding an x that works is 0.

The next step is to show that two graphs with property (*) must be the same, and this is a bit more fiddly. The way to do it is to systematically relabel the vertices of the second graph using the fact that property (*) holds. Imagine that I've already managed to relabel 6 of the vertices of the second graph so that the edges between them are the same as the vertices on the first graph with the same labels. You extend this relabelling to include a 7th vertex as follows. First of all, choose a new vertex x in the first graph. This will be connected to some of the 6 vertices and not to the others. Suppose for the sake of argument its connected to 3 of the 6 vertices and not to the other 3. Call the set of vertices in the 6 that it is connected to U, and the ones it isn't connected to V. Since the second graph has property (*), there will be some vertex y in the second graph connected to all the vertices in U and none of the ones in V. Relabel this vertex in the second graph the same as the 7th vertex in the first graph. Now keep doing this until every vertex in the first graph has a corresponding vertex in the second graph.

The problem is that there might be some leftover vertices in the second graph which don't correspond to anything in the first graph. The way to fix this is by going back and forth from the first graph to the second graph, and then from the second graph to the first graph again, making sure to eventually fill in all the gaps. Going back and forth rather than just going forth from the first to the second ensures that there will be no gaps, because if there were a gap in either graph it would eventually be filled in by this method (as long as you are systematic about the way in which you choose the next vertex to relabel).

To prove that this random graph is the same as the Rado graph is just a matter of showing that the Rado graph has property (*). Have a go.

Confident mathematicians can read more about this in the lecture slides available at Professor Cameron's web page.

- 5 comments by 1 or more people Not publicly viewable

  1. I'm just a lowly second year, but I find the link to probability disturbing.
    You say that two people can construct graphs by choosing two vertices and tossing a coin to decide if they are connected, and then go on to give a rule if we label the vertices, how to construct the graph. This is very misleading, in the first case the chance of ANY two vertices being joined is 1/2, and the chance of two particular vertices being joined is still 1/2. But in the second, the chance of ANY two vertices being joined is indeed 1/2, but once you fix two points doesn't the rule give us an explicit yes/no answer, so the probability of them being joined is either 1 or 0.

    14 Jan 2006, 09:05

  2. I don't see the problem with the above. After all, once you've actually generated a graph by flipping an infinite number of coins, you've then got a fully determined graph, with verticies either joined or not.

    The part I don't understand (from the slides) is:

    A standard ‘back-and-forth’ argument: condition (∗) allows us to extend any partial isomorphism (in either direction) to any further point.

    because I couldn't tell you what a 'back-and-forth' argument is, standard or otherwise, because I don't think I've seen one. I get a vague idea from the quote, but no more than that.

    In any case, it's still a pretty cool theorem, even if I don't quite understand it yet.

    14 Jan 2006, 12:50

  3. Steven, yes you're right and I probably didn't fully make clear that the two graphs will be the same up to relabelling of the vertices. So, having chosen a random graph, there will be a way of relabelling the vertices of your random graph so that its the same as the Rado graph. If you want it fully technically, two graphs (V_1,E_1) and (V_2,E_2) are isomorphic if there is an invertible map f:V_1->V_2 such that if the edge (u,v) is in E_1 then (f(u),f(v)) is in E_2 and the same for f^-1. The theorem says that the two randomly chosen graphs will be isomorphic, not that they'll be exactly the same (which will happen with probability 0).

    Colin, yes that's the bit I'd need to draw some pictures to illustrate, it would be quite difficult to explain using words only. I'm not surprised that you haven't come across a back-and-forth argument before, most people don't. They usually crop up in logic and set theory courses, and I don't think there are any at Warwick.

    14 Jan 2006, 16:34

  4. Also, I will probably write a followup entry with the proof and the pictures at some point in the next few days…

    14 Jan 2006, 16:34

  5. OK, I got round to putting the proof in quicker than I thought. Clear?

    14 Jan 2006, 19:25

Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.
Not signed in
Sign in

Powered by BlogBuilder