= Logarithmic-regime giant component
{title2=$L_1=n-(1+o(1))n^{1-\gamma},\quad p=\gamma\log n/n$}
Fix $k\geq1$, $\gamma_0>1/(k+1)$, and $\gamma_0\leq\gamma\leq1-\omega(n)/\log n$ with $\omega(n)\to\infty$. A <binomial random graph> has one <giant component> of the displayed order and all other <graph components> are <tree components> of orders at most $k$, <with high probability>. The <expected value> and <variance> of the <isolated vertex> count concentrate it around $n^{1-\gamma}\to\infty$. A <Cayley formula> upper bound for connected sets excludes component sizes $k+1$ through a small fixed fraction of $n$; the empty-<graph cut> bound excludes the remaining sizes up to $n/2$. An extra-<edge> count excludes cyclic small <graph components>. The <expected value> of the number of <vertices> in small nonisolated <tree components> is $O(n d e^{-2d})=o(n e^{-d})$, where $d=np$. The <Markov inequality> completes the count of <vertices> outside the unique large <graph component>.
Back to article page
