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.

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.

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.

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.

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.