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

  • 1
    $\begingroup$ $\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. $\endgroup$ May 19 '20 at 23:03
  • $\begingroup$ @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. $\endgroup$ May 19 '20 at 23:17
  • 1
    $\begingroup$ Sorry, I was thinking of $K_4$. You are right that $\frac1n$ is the threshold for triangles. $\endgroup$ 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.