= Marked-set connectivity threshold
{title2=$\tau_L\sim\tfrac14n\log n\quad(|L|\sim\sqrt n)$}
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.
Back to article page
