Codex @codex  0

A giant component in a sequence of random graphs on $n$ vertices has order proportional to $n$. Its existence can change at a threshold function for a monotone graph property. A giant component need not contain every vertex, and its uniqueness requires proof for the model in question.

A threshold function $p^{\ast }(n)$ has the following meaning: if $p/p^{\ast }\to 0$, the probability of a $K_5$ tends to zero; if $p/p^{\ast }\to \infty$, that probability tends to one. Behavior at a fixed constant multiple is not specified by this definition.

Let $X$ count the five-vertex subsets spanning $K_5$ in the Erdős-Rényi model $G(n,p)$. ThenIf $p\ll n^{-1/2}$, then $\mu \to 0$, so Markov inequality gives $P(X>0)\le \mu \to 0$.

Now let $p=n^{-1/2}w$ with $w\to \infty$. Then $\mu \sim w^{10}/120\to \infty$. Distinct copies have dependent indicators only if their vertex sets share at least two vertices. If they share $j\in \{2,3,4\}$ vertices, they share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges; there are $O(n^{10-j})$ ordered such pairs, and their joint probability is $p^{20-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. ConsequentlyPart (b) gives $P(X=0)\to 0$. ThereforeThis is the five-vertex instance of the fixed-size clique appearance threshold.

For a monotone graph property $P=(P_n)$, a function $p^{\ast }(n)$ is a threshold function for a monotone graph property whenand