I’ve been thinking a lot about random graphs this week, so it is appropriate for my post this week to be about them. One of the most important models of random graphs is the Erdős–Rényi model. Here is the construction: we fix some parameter with , and we choose some positive integer . Then, we draw vertices. Between each pair of vertices, we put an edge there with probability , independently of all the other pairs. I’ve been thinking about problems relating to evolutionary dynamics on such graphs, but I won’t describe that today. (Maybe I will at some point, when I understand them better.)
Instead, I just want to talk about the graphs themselves, since there are a lot of questions one can ask about the structure of them. What do they look like? In particular, are they likely to be connected?
The answer is that it depends on how large is relative to . There is a phase change at . In fact, we have the following theorem (which is not quite the best possible):
Theorem (Erdős–Rényi). For any , we have the following:
- If , then the probability that the graph is connected goes to 1, as goes to infinity.
- If , then the probability that the graph is connected goes to 0, as goes to infinity.
I’m not going to give a proof here, but a proof can be found on this MathOverflow page.
But what happens when the graph is disconnected? To what extent does it fail to be connected? There is a very nice answer to this question as well:
Theorem. Suppose that is a constant. Then:
- If , then with high probability all the connected components are small: they have size .
- If , then with high probability there is exactly one large connected component, of size , for some number , and the rest of the connected components have size .
The large component when is called, suitably, the Giant Component. A proof can be find here.
There is a lot more than one can say about the Erdős–Rényi model for random graphs, but this will be enough for now.