I am aiming to write a short post about each lecture in my ongoing course on *Random Graphs*. Details and logistics for the course can be found here.

The goal of the second lecture was to establish the sharp phase transition for the connectivity of the random graph G(n,p(n)) around the critical regime . In the end, we showed that when is any diverging sequence, and , then we have that G(n,p(n)) is *with high probability* not connected.

In the next lecture, we will finish the classification by studying , and show that for this range of p, the graph G(n,p(n)) is with high probability connected.

The details of the lecture, especially the calculation, are not presented fully here. There, I followed van der Hofstad’s recent book fairly closely, sometimes taking different approximations and routes through the algebra, though all versions remain fairly close to the original enumerations by Renyi.

**Immediate remarks**

- One is allowed to be surprised that for almost all scalings of p(n), G(n,p) is either whp connected or whp not connected. The speed of the transition is definitely interesting.
- As defined in lectures, the property that a graph is connected is an
*increasing*property, meaning that it is preserved when you add additional edges to the graph. - Because of the natural coupling between G(n,p) and G(n,q), the fact that connectedness is an increasing property makes life easier. For example, we can insist temporarily that , or whatever scaling turns out to be convenient for the proof, but conclude the result for all diverging . This avoids the necessity for an annoying case distinction.

**Heuristics – Isolated vertices**

It turns out that the ‘easiest’ way for such a graph to be disconnected is for it to have an isolated vertex. In determining that the graph has a *cut* into classes of sizes a and b with no edges between them, there is a trade-off between the number of ways to choose the partition (which increases with min(a,b) ) and the probabilistic penalty from banning the ab edges between the classes (which decreases with min(a,b) ). It turns out that the latter effect is slightly stronger, and so (1,n-1) dominates.

**Method 1: second-moment method**

In the case , we use a *second-moment method* argument to establish that G(n,p) contains an isolated vertex with high probability. Note that a given vertex v is isolated precisely if n-1 edges are not present. Furthermore, two given vertices v,w are *both* isolated, precisely if 2n-3 edges are not present. So in fact, both the first moment and the second moment of the number of isolated vertices are straightforward to evaluate.

It turns out that the number of isolated vertices, , satisfies

(*)

As always, we have to eliminate the possibility that this divergent expectation is achieved by the graph typically having no isolated vertices, but occasionally having very many. So we turn to the second moment, and can show

and so by Chebyshev’s inequality, we have .

**Method 2: first-moment method**

Counter-intuitively, although the case requires only a first-moment method, it is more technical because it involves the non-clear direction of the informal equivalence:

At the time we showed (*), we also showed that for this regime of p(n), G(n,p) whp has no isolated vertices. It remains to show that it has no splits into (unions of) connected components of sizes k and n-k. Continue reading