How to understand graph property thresholds?

Question

Here are some definitions:

Definition 1: A graph property $\cal{P}$ is monotone (increasing) if adding edges preserves $\cal{P}$.
Examples include containing a subgraph $H \subset G$, having $\alpha (G) < k$, connectivity,...

Definition 2: A monotone property $\cal{P}$ is nontrivial if it is not satisfied by the edgeless graph, and is satisfied by the complete graph, i.e. $\mathbb{P}(G(n,0) \in \cal{P}) = 0$, and $\mathbb{P}(G(n,1) \in \cal{P}) = 1$.

Definition 3: Given a nontrivial monotone graph property $\cal{P}$, $p_0(n)$ is a threshold for $\cal{P}$ if $$\mathbb{P}(G(n,p) \in \cal{P}) \to \begin{cases} 0 & \text{if $p << p_0(n)$} \\ 1 & \text{if $p >> p_0(n)$} \end{cases}$$

I'm not sure I understand definition 3. When $p \to 0$, we certainly have $p << p_0(n)$ for any $p_0(n) \in (0,1)$, and since $\cal{P}$ is nontrivial, $\mathbb{P}(G(n,0) \in \cal{P}) \to 0$. Similarly, when $p \to 1$, $\mathbb{P}(G(n,0) \in \cal{P}) \to 1$. So is any $p_0(n) \in (0,1)$ a threshold for $\cal{P}$?

Answer 1

The statement of threshold definition is incorrect. You don't look at the limit for $p$ tending to something. You have a fixed value or function for $p$, then you look at the limit when $n$ tend to infinity :

$$ \lim_{n\to\infty}\mathbb{P}[G(n,p)\in\mathcal{P}] = \begin{cases} 0 & \text{if $p < p_0(n)$} \\ 1 & \text{if $p > p_0(n)$} \end{cases} $$

For instance $p(n)=\frac{\log n}{n}$ is a threshold for graph connectivity. So that $$\lim_{n\to\infty}\mathbb{P}\left[G\left(n,\frac{\log n - \omega(n)}{n}\right)\text{is connected}\right]=0$$ And $$\lim_{n\to\infty}\mathbb{P}\left[G\left(n,\frac{\log n + \omega(n)}{n}\right)\text{is connected}\right]=1$$

You can take $\omega(n)$ as small as you want, as long as it goes to infinity, such as $\log\log n$ if you want.

Note that in this example, $\lim_{n\to\infty}p(n)=\lim_{n\to\infty}\frac{\log n + \log\log n}{n}=0$, however the probability is $1$. $p(n)$ tends to 0, but not fast enough compare to the size of the graph : We keep a smaller and smaller percentage of the edges from $K_n$ into $G(n,p)$, but the total number of edges in $K_n$ increases faster. At one points we will get a connected $G(n,p)$.

Answer 2

You are wrong when you say that if $p \to 0$, then we necessarily have $\Pr[G(n,p) \in \mathcal P] \to 0$.

For example, $p(n) = \frac1n$ is a threshold for the property of having cycles. When $p \ll \frac1n$, $G(n,p)$ is a forest with high probability. When $p \gg \frac1n$, $G(n,p)$ has cycles with high probability. This remains true even if we choose $p = o(1)$. For example, when $p = \frac1{\sqrt n}$, $G(n,p)$ has lots and lots of cycles with high probability.

You are also wrong when you say that if $p \to 1$, then we necessarily have $\Pr[G(n,p) \in \mathcal P] \to 1$, even though this is true for most interesting graph properties (and even though the definition of a threshold isn't set up to deal with properties where this is false).