= Fixed-order tree-component window
{title2=$\omega n^{-k/(k-1)}\leq p\leq[\log n+(k-1)\log\log n-\omega]/(kn)$}
For fixed $k\geq2$ and $\omega\to\infty$, the expected number of <tree components> of order $k$ is asymptotic to $k^{k-2}n^kp^{k-1}e^{-knp}/k!$ throughout the displayed window. It tends to infinity: split $np$ at $1$ and $(\log n)/(2k)$ to obtain lower bounds of orders $\omega^{k-1}$, $\sqrt n$, and $e^\omega$. Distinct overlapping vertex sets cannot both be components; disjoint sets have joint-to-product probability ratio $(1-p)^{-k^2}=1+o(1)$. Thus the relative variance vanishes, proving a component of order $k$ exists <with high probability>.
Back to article page
