= Solution
It suffices to prove the assertion after replacing $\omega$ by $\min\{\omega,\sqrt{\log n}\}$: that replacement gives a tighter interval. Thus assume $\omega\to\infty$ and $\omega=o(\log n)$, and put
$$
p_\pm=\frac{\log n\pm\omega/2}{2n},\qquad
m_\pm=\frac n4(\log n\pm\omega).
$$
At $p_-$, let $J$ count <isolated vertices> in $L$. The same <indicator random variable> calculation as for all <isolated vertices> gives
$$
\mathbb EJ=\ell(1-p_-)^{n-1}=(1+o(1))e^{\omega/4}\to\infty,\qquad
\frac{\operatorname{var}J}{(\mathbb EJ)^2}\leq\frac1{\mathbb EJ}+\frac{p_-}{1-p_-}=o(1).
$$
By the <Chebyshev inequality>, $J>0$ <with high probability>. Since $\ell\geq2$ eventually, the marked <vertices> are then not all connected.
At $p_+$, the <logarithmic-regime giant component> result applies with $k=2$ and any fixed $\gamma_0\in(1/3,1/2)$. Its unique <giant component> misses $(1+o(1))n^{1/2}e^{-\omega/4}$ <vertices>. On the event that it misses at most twice that number, <exchangeability> makes the missed vertex set uniform conditional on its size. A <union bound> therefore gives
$$
\mathbb P(L\text{ meets the complement of the giant})
\leq o(1)+2\ell n^{-1/2}e^{-\omega/4}=o(1).
$$
Thus all of $L$ is connected at $p_+$ <with high probability>.
For the <uniform random graph process>, assign uniform labels to the <edges> of the <complete graph> as <independent random variables> and reveal them in label order. The <binomial random graph> $G(n,p)$ is the prefix containing the $M(p)$ labels at most $p$, where $M(p)$ has a <binomial distribution> with parameters $N=\binom n2$ and $p$. Its <variance> at $p_\pm$ is $O(n\log n)$, whereas the gap between $\mathbb EM(p_\pm)$ and the relevant endpoint $m_\pm$ is $(1+o(1))\omega n/8$. The <Chebyshev inequality> gives $M(p_-)\geq m_-$ and $M(p_+)\leq m_+$ <with high probability>, with harmless integer rounding. The <monotone graph property> that all marked <vertices> are connected now implies
$$
\boxed{\frac n4(\log n-\omega)\leq\tau\leq\frac n4(\log n+\omega)\quad\text{with high probability}.}
$$
The <marked-set connectivity threshold> is lower than the threshold for connecting every <vertex>, because only about $\sqrt n$ specified <vertices> need to avoid the small <graph components>.
Back to article page
