Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


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?

share|cite|improve this question
Assume n is large and fixed, and also fix r, possibly needing 3r < n. Then see how the quantity varies with l. Gerhard "Ask Me About System Design" Paseman, 2011.03.11 –  Gerhard Paseman Mar 11 '11 at 17:57

1 Answer 1

up vote 1 down vote accepted

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


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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.