2
$\begingroup$

In the context of Random graph threshold, in particularin the Uniform Random Graph model (i.e. I am working with the probability space $G_{n,M}$ described in Erdos' paper https://users.renyi.hu/~p_erdos/1959-11.pdf), I want to prove that $m^* = \frac{1}{2}n\log n$ is sharp threshold for the property that a graph on n vertices contains at least one isolated vertex (basically proving lemma 1.11 at page 13 of https://www.math.cmu.edu/~af1p/BOOK.pdf). Note that in this context we are interested to see what happens as $n \to \infty$.

Now in equation (1.9) of that lemma, there is the following product: $$\prod_{i=0}^{m-1} 1-\frac{4i}{n(n-1)(n-2)-2i(n-2)},$$ where $m=\frac{1}{2}n(\log(n)+\omega(n))$ where $\omega(n)=o(\log n)$.

Also in what follows $m=\frac{1}{2}n(\log(n)+\omega(n))$

Now the product turn out to be $\left(1+\mathcal O\left(\frac{(\log n)^2}{n}\right)\right)$. However in this context I just get away with the fact that asymptotically as $n\to \infty$ the product goes to $1$.

I can prove that by reasoning in the following manner: $\prod_{i} (1-f(i))\leq \prod_{i} (1-h(i))$ if $\forall i:h(i)\leq f(i)$.

Now in our case $f(i)=\frac{4i}{n(n-1)(n-2)-2i(n-2)}$ while we can take $h(i)=\frac{4}{n^3+2n(\log(n)+\omega(n))+2n}$

Using the fact that $h(i) \to 0$ as $n \to 0$ I use the asymptotic approximation $(1+z)^\alpha$ valid for small $z$ to get: $$\prod_{i=0}^{m-1} (1-h(i))=\left(1-\frac{4}{n^3}\right)^{\frac{1}{2}n(\log(n)+\omega(n))}=1+\mathcal O\left(\frac{\log n}{n^2}\right)$$

I have dropped the smaller terms in the denominator and $\omega$ by our assumption that $\omega(n)=o(\log n)$.

In a similar manner I can take $g(i) \geq f(i)$ and by reasoning in the same way I get that the product is bounded below by $$\prod_{i=0}^{m-1} (1-g(i))=\left(1+\mathcal O\left(\frac{(\log n)^2}{n}\right)\right)$$

Therefore as $n \to \infty$ I can prove that the product goes to 1 by the sandwich theorem.

However is there a nicer and quicker way to prove that the product is $$\left(1+\mathcal O\left(\frac{(\log n)^2}{n}\right)\right)$$

$\endgroup$

1 Answer 1

2
$\begingroup$

To begin with, as soon as I see the expression, I want to clean up the denominator before doing anything else. Since $0 \le i < m < \frac12 \binom n2$, we have $$ \frac12 n(n-1)(n-2) \le n(n-1)(n-2) - 2i(n-2) \le n(n-1)(n-2), $$ and therefore $$ \frac{4i}{n(n-1)(n-2)} \le \frac{4i}{n(n-1)(n-2) - 2i(n-2)} \le \frac{8i}{n(n-1)(n-2)}. $$ We will not care about the constant $4$ versus $8$, so both bounds are as tight as we need them to be.

For the lower bound, we simply have $$ \prod_{i=0}^{m-1} \left(1 - \frac{8i}{n(n-1)(n-2)}\right) \ge 1 - \sum_{i=0}^{m-1} \frac{8i}{n(n-1)(n-2)} = 1 - \frac{8\binom m2}{n(n-1)(n-2)} $$ and this is clearly $1 + O(\frac{(\log n)^2}{n})$. (Why the relationship between the product and the sum? Because multiplying a number less than $1$ by a factor $1-p$ decreases it by at most $p$.)

In particular, for $n$ sufficiently large, our product always stays above $\frac12$. Multiplying a number greater than $\frac12$ by a factor $1-p$ decreases it by at least $\frac p2$, so we have the upper bound $$ \prod_{i=0}^{m-1} \left(1 - \frac{4i}{n(n-1)(n-2)}\right) \le 1 - \frac12\sum_{i=0}^{m-1} \frac{4i}{n(n-1)(n-2)} = 1 - \frac{2\binom m2}{n(n-1)(n-2)} $$ and this is also clearly $1 + O(\frac{(\log n)^2}{n})$.

A more precise version of this argument (replacing the initial bound of $m < \frac12 \binom n2$ by $m < \epsilon \binom n2$, and saying that our product stays above $1-\epsilon$ rather than above $\frac12$ when $n$ is sufficiently large) actually tells us that the error term is not just $O(\frac{(\log n)^2}{n})$ but $(1+o(1)) \frac{2m^2}{n^3}$.

$\endgroup$
2
  • $\begingroup$ Thanks Misha. I guess one thing to notice also is that since it is a product of infinite terms $\leq 1$, then the upper bound must be $\leq 1$ anyway $\endgroup$ Apr 8, 2018 at 21:23
  • $\begingroup$ Right, and I suppose I implicitly use that along the way in the proof of the lower bound. $\endgroup$ Apr 8, 2018 at 21:28

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.