A graph $G(n,p)$ has $\Omega(k^2)$ edges of a special type, $k \in \mathbb{Z}^+$. If $p = \omega(k^{-2})$, then w.h.p. one of the edges is in $G$.

Question

Why is it so? I know that the probability that none of those edges appears in the graph is $(1-p)^{k^2}$, but not sure how to continue with the reasoning.

Answer 1

Use the inequality $1 - p \le e^{-p}$.

This lets us bound the probability by $e^{-pk^2}$, and $pk^2 \to \infty$ (and therefore $e^{-pk^2} \to 0$) as... $k \to \infty$?

Usually "with high probability" refers to probability tending to $1$ as $n \to \infty$. So in this case, if $k$ and therefore $p$ are constant as $n \to \infty$, this is not quite okay, but we're fine assuming $k$ tends to infinity with $n$.