It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is asymptotically almost surely connected. The way I know how to prove this is (1) first counting the expected number of components of order $2, 3, \dots, \lfloor n/2 \rfloor$, and seeing that the expected number is tending to zero. Then (2) showing the expected number of isolated vertices is also tending to zero.
This approach also allows more precise results, such as: if $p = (\log{n}+c) / n$ with $c \in \mathbb{R}$ constant, then Pr$[G(n,p)$ is connected] $\to e^{-e^{-c}}$ as $n \to \infty$, which follows once we know that in this regime the number of isolated vertices is approaching a Poisson distribution with mean $e^{-c}$.
I am wondering if it is possible to
give an easier proof (of a coarser result) along the
following lines. There are $n^{n-2}$
spanning trees on the complete graph,
and $G$ is connected if and only if
one of these trees appears. So the
expected number of spanning trees
is $n^{n-2}p^{n-1}$. One might expect that if this
function is growing quickly enough,
then with
high probability $G(n,p)$ is connected.
I think I remember reading somewhere that this approach doesn't quite work — for example the variance is too large to apply Chebyshev’s inequality. What I am wondering is if there is some way to fix this if we are willing to make $p$ a little bit bigger. In particular, what about $p = C \log{n} / n$ for some large enough constant $C > 1$, or even $p = n^{-1 + \epsilon}$ for fixed but arbitrarily small $\epsilon >0$?
Best Answer
A nice question. Here's a strategy that occurs to me, though it could fail miserably.
The basic problem seems to be what you said about variance: the appearances of different spanning trees are far from independent, since it is possible to make local modifications to a spanning tree and get another one. (For example, if x is a leaf joined to y, which is joined only to z, then we can replace the path zyx by the path zxy.)
One way we might try to defeat this is to choose a random set $\Sigma$ of spanning trees, where each spanning tree is chosen independently with probability $\alpha^{n-1}$ for some carefully chosen $\alpha$ (which I imagine as a small negative power of $n$). Then the expected number of trees from $\Sigma$ in a $p$-random graph is $(\alpha p)^{n-1}n^{n-2}$, which is pretty large even when $p$ is pretty close to $n^{-1}$. But now we might expect that any two trees in $\Sigma$ are quite well-separated, so perhaps it is possible to get a decent estimate for the variance.
Actually, it's not clear to me what passing to the random set really achieves here: maybe a simpler method (but not wholly simple) is to work out the expected number of pairs of spanning trees by carefully classifying what they can look like. The hope would be that if you pick one tree at random, then the proportion of trees that overlap with it to any great extent is usually so small that the expected number of pairs is not significantly bigger than the square of the expected number of spanning trees. With $p=n^{-1+\epsilon}$ something like this might work, but you've probably already thought about this.