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?



Proof of the clique-number for random graphs: How to bound this binomial-like expression?
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$.


