Proof of the clique-number for random graphs: How to bound this binomial-like expression?

Question

Hello!

Background: I am trying to understand a proof in

Béla Bollobás, Random Graphs, 2nd edition, Ch. 11.1

about the clique number of G(n,p) random graphs.

The problem: At some point, the following sequence is defined:

$F_\ell := \frac{\binom{r}{\ell} \binom{n-r}{r - \ell} } {\binom{n}{r}} (p^{-\binom{\ell}{2}} - 1)$

Afterwards, it is said that

"Routine and crude calculations show that, if $n$ is sufficiently large and $3 \leq \ell \leq r-1$, then $F_\ell < F_3 + F_{r-1}$"

It looks like $F_\ell$ is first decreasing and then increasing, such that it is either bounded by $F_3$ or $F_{r-1}$. However, I do no not see how to show this formally? Especially in the context, where $r = r(n) = \mathcal{O}(n^{\frac13})$ and $p = p(n), 0 < p < 1$ such that

$\binom{n}{r}p^{\binom{r}{2}} \to \infty$ and $\binom{n}{r+1}p^{\binom{r+1}{2}} \to 0$ for $n \to \infty$ holds (as stated in Theorem 11.6 by Bollobas).

In fact, it seems very difficult to say something about these expression as $p(n)$ is specified only implicit by these expectations and $r$ is also depending on $n$.

Does anyone have an idea?

Answer 1

If I remember correctly, I convinced myself of a very similar statement in the Alon/Spencer book (but there even the sum of the intermediate $F_l$ had to be dominated by $F_3+F_{r-1}$) by looking at the quotient

$$\frac{F_{l+1}}{F_l}=\frac{(r-l)^2}{(l+1)(n-2r+l+1)}\frac{\left(p^{-\binom{l+1}{2}}-1\right)}{\left(p^{-\binom{l}{2}}-1\right)}\sim\frac{(r-l)^2}{(l+1)(n-2r+l+1)}p^{-l}.$$

For small $l$ (something like $l\leqslant\log_{1/p}n$) the quotient is less than 1 (so $F_l$ is decreasing in $l$), and for large $l$ the quotient is increasing. So in any case it's sufficient to look at the extreme values of $l$.