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.


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

  • $\begingroup$ 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. $\endgroup$ – blanchey Apr 9 '19 at 17:35
  • 1
    $\begingroup$ 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})$. $\endgroup$ – Misha Lavrov Apr 9 '19 at 20:08

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.