= Persistence of unsampled graph components
{title2=$N_{[k,Dk)}\geq\alpha n\Rightarrow N_{[k,Dk)}\geq\beta n\text{ later}$}
Fix positive $\alpha$, $D\geq2$ and $B>0$. Suppose a size band $[k,Dk)$ of an <Achlioptas process> contains at least $\alpha n$ <vertices> at time $m$. For every fixed $k$, at least $\beta n$ of those <vertices> remain in unchanged <graph components> throughout the next $T=\lceil Bn/k\rceil$ steps, <with high probability>, where one may take $\beta=\alpha e^{-16BD}/4$. This is a deliberately nonoptimal positive constant.
For independent uniform candidate <edges>, an initial <graph component> with $w<Dk$ <vertices> is untouched if none of the $2T$ candidate <edges> meets it. A uniform <edge> hits it with <probability> at most $3w/n$. For sufficiently large $n$, $(1-3w/n)^{2T}\geq e^{-16BD}$, so the <expected value> of the untouched vertex mass $Y$ is at least $\alpha e^{-16BD}n$. Replacing one row of two candidate <edges> can change $Y$ by at most $8Dk$, because only the initial <graph components> hit by an old or new endpoint can change status. The <McDiarmid inequality> therefore makes $Y\geq\alpha e^{-16BD}n/2$ except on an event of <probability> $e^{-c n/k}$, for a positive constant $c$ depending only on $\alpha,B,D$. An untouched <graph component> stays unchanged whichever offered <edge> is selected.
For candidates restricted to absent <edges>, generate each by an independent uniform proposal stream and reject already present <edges>. During any interval of $O(n)$ steps with $O(n)$ present <edges>, each proposal has rejection <probability> $O(1/n)$ conditional on the past. The number of rejections is at most $O(\log n)$ except on an event of <probability> smaller than any inverse power of $n$: if there were $r$ rejections among $2T+r$ proposals, a <union bound> over their positions bounds this by $\binom{2T+r}r(C/n)^r$. The first $2T$ proposals are independent and give the previous untouched-mass estimate. Extra proposals can touch at most $2r$ additional initial <graph components>, losing only $O(Dk\log n)=o(n)$ <vertices> for fixed $k$. This leaves the stated $\beta n$ bound. A <union bound> makes these estimates simultaneous over starting times $m\leq3n$. They hold through the entire interval, so deterministic or random stopping times within it are allowed.
Back to article page
