# Can non-monotone properties of random graphs have a sharp threshold?

I'm working with a random variable on a random graph $$G_{n,p}$$ that has to do with the number of verticies of degree $$1$$, but it's not a monotone property (since adding edges can both make a vertex degree 1 and also make a vertex not degree 1 anymore)

And I know it's proven that monotone properties have a sharp threshold, but I was wondering if it's possible for non-monotone properties (especially the existence of a degree 1 vertex I'm looking at) to have a threshold/sharp threshold.

## 1 Answer

It's possible, it's just not automatically guaranteed.

In the case of a degree $$1$$ vertex, technically there is no threshold because for $$p=0$$ and very small $$p$$, there are no such vertices, for $$\frac1{n^2} \ll p \ll \frac{\log n}{n}$$, they exist with high probability, and for $$\frac{\log n}{n} \ll p$$, once again they do not exist with high probability. But $$\frac{\log n}{n}$$ is a threshold (a sharp one, in fact) if we only consider values of $$p$$ that aren't ridiculously small.

We just have to make sure that when we're proving this threshold, we're careful about monotonicity. The property "there are vertices of degree $$\le 1$$" is monotone, and so we can assume that once these disappear for some $$p$$, they disappear for all larger $$p$$ as well; but we'll have to be careful about sparse random graphs.

If $$X$$ is the number of degree $$1$$ vertices, then $$\mathbb E[X] = n(n-1)p(1-p)^{n-2} \sim n^2p e^{-np}$$ (for $$p \ll \frac1{\sqrt n}$$), and $$\mathbb E[X^2] = \underbrace{\mathbb E[X]}_{\text{diagonal terms}} + \underbrace{n(n-1)p(1-p)^{2n-4}}_{\text{isolated edges}} + \underbrace{n(n-1)(n-2)^2 p^2 (1-p)^{2n-5}}_{\text{other degree 1 pairs}}$$ so $$\text{Var}[X] = n(n-1)p(1-p)^{n-2} + n(n-1)p(1-p)^{2n-4} - (3n-4) p^2(1-p)^{2n-5}$$ which means $$\text{Var}[X] \lesssim 2n^2 p e^{-np}$$ (for $$p \ll \frac1{\sqrt n}$$). In the range where $$\mathbb E[X] \to \infty$$ (to be determined later), we conclude $$\text{Var}[X] \ll \mathbb E[X]^2$$, and therefore $$X \sim \mathbb E[X]$$ with high probability.

We consider several cases:

• When $$(1+\epsilon)\frac{\log n}{n} \le p \ll \frac{(\log n)^2}{n}$$, we have $$e^{np} \ge n^{1+\epsilon}$$, so $$\mathbb E[X] \lesssim n^{1-\epsilon}p \ll n^{-\epsilon} (\log n)^2 \to 0$$. With high probability there are no vertices of degree $$1$$. By a similar expected value argument there are no isolated vertices either.
• For $$p$$ larger than this, there are no vertices of degree $$\le 1$$ by monotonicity of this property.
• When $$\frac1n \ll p \le (1-\epsilon)\frac{\log n}{n}$$, we have $$e^{np} \le n^{1-\epsilon} \ll n$$, so $$\mathbb E[X] \gg np \to \infty$$. Since we have concentration, with high probability there are many vertices of degree $$1$$.
• When $$\frac1{n^2} \ll p \le \frac cn$$, we have $$e^{np} \le e^{-c}$$, so $$\mathbb E[X] \gtrsim n^2p e^{-c} \to \infty$$. Since we have concentration, with high probability there are many vertices of degree $$1$$.

So $$\frac{\log n}{n}$$ is a sharp threshold assuming $$p \gg \frac1{n^2}$$ (that is, that the number of edges is going to infinity).

• Thank you for this wonderful answer! Beautifully said. I am actually now looking, for the purpose of seeing when this is approximately a poisson asymptotically, when the expectation of degree 1 verticies is a positive finite constant. How would I able to identify this? Even the existence of these such functions or a series approximation would be great. – blanchey Apr 9 at 17:35
• Looking back at $\mathbb E[X] \sim n^2p e^{-np}$, we get that when $p = \frac{\log n + \log \log n + c}{n}$ (maybe up to an error that's $\ll \frac1n$), the expected number of degree $1$ vertices is $\mathbb E[X] \sim e^{-c}$, and it can be shown that the distribution is asymptotically $\text{Poisson}(e^{-c})$. – Misha Lavrov Apr 9 at 20:08