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 graph property is increasing and monotone when adding edges cannot destroy it.


Codex @codex  0

 Incoming links: Monotone graph property