I need to show that $$\sum_{i=0}^{m} \binom{m}{m-i}\binom{m^2-m}{i} (1-p)^{\binom{i}{2} + i m} \bigg/ \binom{m^2}{m} (1-p)^{\binom{m}{2}} \to 0$$ as $m \to \infty$, where $p = \frac{1}{m}$, and the denominator extends all the way up to the arrow.
This is in order to show that a random graph drawn from $G_{n, p=1/\sqrt{n}}$ has an independent set of size $m = \sqrt{n}$ with high probability; I am using Chebyschev's inequality where the random variable is $X$ the number of independent sets of size $\sqrt{n}$, and the expression is $\mathbb{E}(X(X-1)) / \mathbb{E}(X)^2$, which we are attempting to send to $0$ in order to show that $\mathbb{P}(X=0) \to 0$. I have already shown that the mean (that is, the denominator of the displayed expression) goes to $\infty$ as $n \to 0$.
Mathematica suggests it goes to $0$ very slowly; certainly my simple attempts to bound the sum by a geometric series have failed. The obvious thing to use is the fact that $\left( \frac{a}{b} \right)^b \leq \binom{a}{b} \leq \left(\frac{ae}{b}\right)^b$; this yields the summand $$\left(\frac{(m-1) e}{i} \right)^i \left(\frac{(m-1) e}{m-i} \right)^{m-i} \left(\frac{m-1}{m}\right)^{i(i-1)/2 - m(m-1)/2 + i m}$$ which Mathematica suggests does not converge any more.
The problem is mainly that the convergence is rather delicate. Even using that $\frac{m-1}{m} \leq 1$ has a large effect on the overall sum, for example. However, I'd expect convergence to be fairly robust, because I happen to know already that there is even an independent set of size $\sqrt{n} \log(n)$ with high probability, not just of size $\sqrt{n} = m$.
Ideas welcome about:
- how to approach the problem better
- how to bound the sum
- mistakes I have made.