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

Question

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.

Answer 1

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