Computations on Bollobas' proof of the $\chi(G(n,p))$ for constant $p$

Question

In Bollobas' proof of the chromatic number of random graphs with constant $p$, he computes the value $r \in \mathbb{R}$ for which the expected number of $r$-cliques in $G(n,p)$ is exactly one:

Given $\binom{n}{r} p^{\binom{r}{2}} = 1$, I want to obtain an expression for $r$.

In particular, applying Stirling approximation $$n! \sim \sqrt{2 \pi n} (n/e)^n$$ We see that

$\binom{n}{r} p^{\binom{r}{2}} \sim (2 \pi)^{-1/2} n^{n+1/2} (n-r)^{-n+r-1/2} r^{-r-1/2} p^{r(r-1)/2}$

So, my aim is to isolate $r$ in:

$(2 \pi)^{-1/2} n^{n+1/2} (n-r)^{-n+r-1/2} r^{-r-1/2} p^{r(r-1)/2} = 1$

Setting $b = 1/p$, I know the answer I should get is:

$r = 2 \log_b n - 2 \log_b \log_b n + 2 \log_b\left(\frac{e}{2}\right) + 1 + o(1)$

However... I dont know how can I do it. I would be grateful if someone can help me!

Thanks!

Answer 1

Go back to the original equation: $\binom nr p^{r(r-1)/2}=1$ and rewrite it as $b^{r(r-1)/2}=n^r/r!\left[\binom nr/(n^r/r!)\right]$.

Notice that $b^{r(r-1)/2}$ becomes larger than $n^r$when $b^{(r-1)/2}>n$. That is when $r=O(\log n)$. Notice that the term in brackets is very close to 1 in that range (certainly between $1/2$ and 1 for large $n$)$.

Hence the solution to the equation satisfies $b^{r(r-1)/2}=An^r/r!$ for some $1/2 < A < 1$. Now take logs to base $b$: $r(r-1)/2=\log_b A+r\log_b n-r\log_b r+r\log_b e+O(1)$. Divide through by $r/2$ to get $r-1=2\log_b n-2\log_b r+2\log_b e+O(1/r)$ or $$r=2\log_b n-2\log_b r+2\log_b e+1+o(1).$$

A great way to solve equations like this (where the RHS changes much slower than the LHS) is iteratively. You start with a guess and plug it in to the right side of the equation to get an improved guess (this is just the Banach contraction mapping theorem in action).

Here start with $r=2\log_b n$. The first improved version is $r=2\log_b n-2\log_b(2\log_b n)+2\log_b e+1+o(1)$. This is exactly the expression you were looking for.

Notice that the approximate solution changed by approximately $2\log_b(\log_b n)$. If you were to compute the next iterate, it would change by the derivative of the RHS times this amount, which is $o(1)$. The subsequent changes decay like a geometric progression with ratio $\log\log n/\log n$, so can be incorporated in the $o(1)$ term.