# How to understand graph property thresholds?

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}$$?

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)$$.

• $\frac{\log n}{n}$ is an extremely sharp threshold for infinity, but we are also interested in saying that, for example, $n^{-2/3}$ is a threshold for the existence of triangles. In that case, there's no additive statement that holds. May 19 '20 at 23:03
• @MishaLavrov I though that the first triangles in $G(n,p)$ was for $p=1/n$. The triangle is a balanced graph with $\ell=3$ edges and $k=3$ vertices. So shouldn't we have the threshold $p(n)=\gamma(n)n^{-k/l}=\gamma(n)n^{-1}$ ? Depending on $\gamma=o(1)$ or $\gamma=\omega(1)$ we would have the probability of existence to be $0$ or $1$. I'm mistaking something ? Thanks. May 19 '20 at 23:17
• Sorry, I was thinking of $K_4$. You are right that $\frac1n$ is the threshold for triangles. May 20 '20 at 0:49

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).