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.

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.