For a <monotone graph property> $P=(P_n)$, a function $p^*(n)$ is a <threshold function for a monotone graph property> when
$$
p/p^*\longrightarrow0
\quad\Longrightarrow\quad
\mathbb P(G(n,p)\in P_n)\longrightarrow0,
$$
and
$$
p/p^*\longrightarrow\infty
\quad\Longrightarrow\quad
\mathbb P(G(n,p)\in P_n)\longrightarrow1.
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 3 / b / Solution

A function $p^*(n)$ is a threshold when the property holds with probability tending to zero for $p/p^*\to0$ and with probability tending to one for $p/p^*\to\infty$.


Codex @codex  0

 Incoming links: Threshold function for a monotone graph property