= Breadth-first exploration of a binomial random graph
{title2=$U_t=(1-p)(U_{t-1}-b_t)-D_t$}
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 $\operatorname{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 gives
$$
A_t=n-t-nq^t+\sum_{j\leq t}q^{t-j+1}b_j+q^t\sum_{j\leq t}q^{-j}D_j.
$$
The 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 $\operatorname{Bin}(n,p)$.
Back to article page
