Erdős-Rényi model

In the $G(n,p)$ model, each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges is included independently with probability $p$.

During breadth-first search of $G(n,p)$ let $U_t$ count unseen vertices, $A_t$ active vertices, and $t$ explored vertices. When $A_{t-1}=0$ start a new unseen root, recorded by $b_t=1$; otherwise $b_t=0$. The newly discovered count is conditionally $\mathrm{Bin}(U_{t-1}-b_t,p)$. Subtract its conditional mean to obtain a martingale difference $D_t$. With $q=1-p$, $U_0=n$ and $A_0=0$, iteration givesThe last sum is a martingale. Positive $A_t$ over an interval means that the graph component under exploration does not finish there. Independently adding phantom children couples each component exploration below a binomial branching process with offspring law $\mathrm{Bin}(n,p)$.

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.

In a uniform random graph process, realize edge arrivals by independent continuous uniform times. For a fixed set of $r$ vertices to form an isolated clique at some time, all $e=\left(\genfrac{}{}{0ex}{}{r}{2}\right)$ internal edges must arrive before the first of the $r(n-r)$ outgoing edges. Their relative arrival ordering is uniform, so the exact probability isA union bound over the vertex sets therefore bounds the probability that such an isolated clique ever appears by $\left(\genfrac{}{}{0ex}{}{n}{r}\right)/\left(\genfrac{}{}{0ex}{}{r(n-r)+e}{e}\right)$. For fixed $r\ge 4$ this is $O(n^{r-e})\to 0$, since $e>r$. This argument controls all process times at once, including the short interval during which an isolated component could exist, without discretizing time.

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.

For $X_j$ the number of tree components of order $j$ in a binomial random graph, choose their vertices, choose one of $j^{j-2}$ labelled trees by the Cayley formula, require its $j-1$ edges, and exclude both the remaining internal edges and all crossing edges. For $j=1$ interpret $j^{j-2}=1$, recovering the isolated vertex count. If $p=\lambda /n$ for fixed positive $\lambda$ and $j=O(\log n)$, the Stirling formula gives $\mathbb{E}{X}_j\sim n(\lambda e^{1-\lambda }{)}^j/(\lambda \sqrt{2\pi }{j}^{5/2})$. Distinct overlapping vertex sets cannot both be graph components; for disjoint sets their joint occurrence gains the factor $(1-p{)}^{-j^2}$ relative to the product, because their between-set edges must be absent only once.

For fixed $k\ge 2$ and $\omega \to \infty$, the expected number of tree components of order $k$ is asymptotic to $k^{k-2}{n}^k{p}^{k-1}{e}^{-knp}/k!$ throughout the displayed window. It tends to infinity: split $np$ at $1$ and $(\log n)/(2k)$ to obtain lower bounds of orders ${\omega }^{k-1}$, $\sqrt{n}$, and $e^{\omega }$. Distinct overlapping vertex sets cannot both be components; disjoint sets have joint-to-product probability ratio $(1-p{)}^{-k^2}=1+o(1)$. Thus the relative variance vanishes, proving a component of order $k$ exists with high probability.

A graph property is increasing and monotone when adding edges cannot destroy it.

A function $p^{\ast }(n)$ is a threshold when the property holds with probability tending to zero for $p/p^{\ast }\to 0$ and with probability tending to one for $p/p^{\ast }\to \infty$.

Assign an independent uniform label $U_e$ to every possible edge and include $e$ in $G(n,p)$ exactly when $U_e\le p$. This couples all edge probabilities so that $p\le q$ implies $G(n,p)\subseteq G(n,q)$.

Sprinkling exposes independent rounds $G(n,p_1),\dots ,G(n,p_k)$. Their union has distribution $G(n,p)$ where

Let $N$ be the number of isolated vertices in $G(n,p)$. Indicator variables giveand, because a specified pair is simultaneously isolated precisely when the $2n-3$ incident edges are absent,

For $p=c\log n/n$, the number $N$ of isolated vertices satisfiesThe upper side follows from the first-moment bound. On the lower side, $\mathbb{E}N\to \infty$ and $\mathrm{var}(N)/(\mathbb{E}N{)}^2\to 0$, so the second-moment method applies.

For every fixed $\epsilon >0$,whereas the probability tends to zero when $p\le (1-\epsilon )\log n/n$. Above the threshold a union bound excludes every component of size at most $n/2$; below it isolated vertices remain with high probability.

A disconnected binomial random graph has a connected component of a graph with at most half its vertices. The union bound over its possible vertex sets givesThe final geometric series bound tends to zero for fixed $p>0$.

For fixed real $c$, the number of isolated vertices in a binomial random graph with $p=(\log n+c)/n$ converges to a Poisson distribution of mean $e^{-c}$. Its fixed factorial moments tend to $(e^{-c}{)}^k$. A union bound for small connected components, together with exclusion of intermediate components, shows that isolated vertices are asymptotically the only obstruction to connectivity. Thus the displayed limit is the zero-mass of that Poisson distribution.

If a fixed graph $H$ has $v$ vertices, $e$ edges, and $N_H(n)$ unlabelled copies in $K_n$, then the number $X_H$ of its copies in $G(n,p)$ satisfiesThis follows by writing $X_H$ as a sum of indicator random variables.

For $p=n^{-2/3}\log n$, the number $X$ of copies of $K_4$ satisfiesand $\mathrm{var}(X)=o((\mathbb{E}X{)}^2)$. Two distinct copies have dependent indicators only when they share at least two vertices; pairs sharing two or three vertices contribute respectively $O(n^6{p}^{11})$ and $O(n^5{p}^9)$ to the variance.

If $H$ is formed by attaching one pendant edge to a fixed clique, each copy has a unique clique core. Its number of extensions is the number of ambient edges from that core to outside vertices. At a scale where the core count is tight and its expected extension count diverges sufficiently rapidly, a Chernoff bound uniformly over all possible cores shows that the total count, divided by the extension mean, has the same limiting law as the core count. Non-induced copies are intended; extra ambient edges are not forbidden.

For $p=n^{-2/3}\log n$, the expected number of pairs of $K_4$ copies sharing a vertex isThus, with probability tending to one, all the $K_4$ copies are vertex-disjoint. Together with sparse clique-count concentration, this gives arbitrarily many vertex-disjoint copies with probability tending to one.