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!



Computations on Bollobas' proof of the $\chi(G(n,p))$ for constant $p$
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.


