Parametrization of probability in a limit for a random graph

Question

I don't understand the part where the authot exchanges $p$ for $c/n$. This can only work if $c$ is a function of $n$ namely $pn$.

I hope somebody can tell me what the author is doing here and why he is allowed to first take $n\rightarrow\infty$ and then $c\rightarrow 0$ even though if $n\rightarrow \infty$ then automatically $c\rightarrow \infty$.

Can also someone tell me how the author comes to the conclusion that if $p=10^{-6}/n$ then $G(n,p)$ is unlikely to have a triangle and also how the second conclusion that if $p=10^6/n$ then $G(n,p)$ is likely to have a triangle is even possible ? For example if $n<10^6$ then $p>1$ but this is not possible because $p$ is a probability ranging from 0 to 1.

Answer 1

Lots to explain here. Hope the following helps.

First, the parametrization of $G(n,p)$ as $p=c/n$ is a standard parametrization, sometimes called the coarse parametrization if $c$ is a constant. It just means that we define $c=pn$ and we will study different regimes of $G(n,p)$ depending on the value of $c$. For instance, its common to look for properties of $G(n,p)$ depending on the three cases $c<1$, $c=1$ and $c>1$. In general $c$ will be a function of $n$ indeed, but studying the case where $c$ is a constant often helps us understand how the general case behaves.

It is not true that $c\to\infty$ automatically when $n\to\infty$. For instance you could have :

• $p=\frac{\log n}{n}$ and $c(n)=\log n$, then $c\to\infty$ when $n\to\infty$
• $p=1/ n^2$ and $c(n)=1/n$, then $c\to 0$ when $n\to\infty$
• $p=2/n$, then $c$ is a constant.

But in here, the author does not assume the asymptotic of $c(n)$. When he states the two different cases ($c\to 0$ and $c\to\infty$), it is to present the following fact :

If you have $p=c/n$, with $c$ a constant, then you know that the limit probability of having no triangle is exactly $e^{-c^3/6}$. Therefore if $p=c/n$ where $c$ is a very small constant, then the limit probability of having no triangle will be very close to $1$. If $c$ is very large, then the limit probability of having no triangle will be very close to $0$.

The author does not value $$\lim_{n\to\infty} \lim_{c\to } \mathbb{P}[X=0]$$ He says, assume $p=c/n$, then $$\lim_{c\to 0} \lim_{n\to\infty} \mathbb{P}[X=0] = 1$$ and $$\lim_{c\to \infty} \lim_{n\to\infty} \mathbb{P}[X=0] = 0$$

This is why the author say that if $p=10^{-6}/n$, then the probability of no triangle is almost 1 : $$\lim_{n\to\infty} \mathbb{P}[X=0]=e^\frac{-c^3}{6}\approx 1$$

This helps concluding on the other cases as follow. Assume that $p=n^{-0.9}$. You can take $c$ a constant as large as you want, for $n$ large enough you will have $p>c/n$. Therefore because we know the limit probability when $c$ is constant is $e^{-c^3/6}$ which tends to $0$ when $c\to\infty$, then we know $\lim_{n\to\infty} \mathbb{P}[X=0]=1$. (caveat : we need some details on the monotonicity of the probability to make this argument formal.) You conclude on the other case $p=1/(n \ln n)$ in the same way with $p<c/n$ for $c$ as small as you want.

Regarding your last remark, it's true that $p$ is ill-defined if $n<10^6$, but we are only interested in asymptotic ($n\to\infty$), so you can assume " $n$ is large enough".