Uniform random graph process ($G_{n,m}$)

Start with the empty graph and reveal the edges of the complete graph in a uniformly random order. After $m$ steps its edge set is a uniform $m$-element subset. Independent uniform edge labels couple this process with all binomial random graphs: $G(n,p)=G_{n,M(p)}$, where $M(p)$ has a binomial distribution with parameters $\left(\genfrac{}{}{0ex}{}{n}{2}\right),p$. For a monotone graph property, concentration of $M(p)$ transfers a threshold estimate between edge probability and edge count.

Couple the process with independent uniform edge labels, and expose $p_{-}=(\log n-\frac{1}{4}\log \log n)/n$. A spanning-tree union bound excludes components of orders $2$ through $n/\log n$, and a cut bound excludes orders up to $n/2$. The graph has one large component and at most $\log n$ isolated vertices, with at least one isolated vertex. Before $p_{+}=(\log n+\frac{1}{4}\log \log n)/n$, the probability of any new edge between those isolated vertices is $O((\log n{)}^2\log \log n/n)=o(1)$. All have joined the large component by $p_{+}$ by the isolated-vertex threshold in the Erdős-Rényi model. Throughout this window the only obstruction to connectivity is an isolated vertex, establishing the equality of hitting times.

For a fixed set $L$ of $\lfloor \sqrt{n}\rfloor$ vertices, let ${\tau }_L$ be the first step at which they all belong to one graph component. In the uniform random graph process, ${\tau }_L$ lies between $n(\log n-\omega )/4$ and $n(\log n+\omega )/4$ with high probability for every $\omega \to \infty$. Below that scale the marked isolated vertex count has divergent expected value and small relative variance. Above it the logarithmic-regime giant component misses $o(\sqrt{n})$ vertices; exchangeability and a union bound show that none are marked. The label coupling then transfers the two assertions to the process.