# simple algebraic problem (related to graph theory)

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!

(By the way, this is part of Bollobas' proof for the chromatic number of $G(n,p)$ with $p$ constant)

Thanks!

-
Is there any condition for $p$? I guess you need an asymptotic when $n\to\infty$. –  Frank Science Jul 15 '12 at 15:04
In this case, $p$ is a fixed real number: $0 < p < 1$. In particular, it corresponds to the probability of each possible edge of being present in a random graph $G \sim G(n,p)$. –  Walkland Jul 15 '12 at 15:43

Firstly, we have $0<r\le n$. As a direct result of Stirling's approximation, we have $$\ln n!=n\ln n-n+\frac12\ln n+O(1)\tag1$$ Take logarithm at $\binom nrp^{\binom r2}=1$, we have $$\ln\binom nr+\binom r2\ln p=0$$ For $0<p<1$, let $c=-\ln p$, and $b=1/p$, we have $c>0$, therefore $L=\frac c2r(r-1)$ where $$L=\ln\binom nr$$ We apply a rough approximation at first: $$L=n\ln n-r\ln r-(n-r)\ln(n-r)+O(n)$$ therefore $L=O(n\log n)$, which results in $r=O(\sqrt{n\log n})=o(n)$. Now observe more closely $$L=(n\ln n-n)-(r\ln r-r)-((n-r)\ln(n-r)-(n-r))+O(\log n)$$ and $\ln(n-r)=\ln n+\ln(1-r/n)$, thus $$L=r\ln n-r\ln r-(n-r)\ln(1-r/n)+O(\log n)$$ therefore $\frac c2(r-1)=O(\log n)$ and $r=O(\log n)$. Now we apply approximation (1), more exact than the proceding approximations: \begin{multline} L=\left(n\ln n-n+\frac12\ln n\right)-\left(r\ln r-r+\frac12\ln r\right)\\ -\left((n-r)\ln(n-r)-(n-r)+\frac 12\ln(n-r)\right)+O(1) \end{multline} Simplify it, we get $$L=r\ln n-r\ln r-(n-r)\ln(1-r/n)-\frac12\ln r-\frac12\ln(1-r/n)+O(1)$$ Notice that $\ln(1-r/n)=-r/n+O(r/n)^2=O(1)$, and we have $$L=r\ln n-r\ln r+r-\frac12\ln r+O(1)$$ At first, go roughly $$L=r(\ln n+O(\log r))=r(\ln n+O(\log\log n))$$ thus $$\frac c2(r-1)=\ln n+O(\log\log n)\implies r=\frac{2\ln n}c+O(\log\log n)$$ then go exactly $$L=r\ln n-r\ln r+r+O(\log\log n)$$ thus $$\frac c2(r-1)=\ln n-\ln r+1+O\left(\frac{\log\log n}{\log n}\right)$$ where \begin{align} \ln r &=\ln\left(\frac{2\ln n}c+O(\log log n)\right)\\ &=\ln\left(\frac{2\ln n}c\right)+\ln\left(1+O\left(\frac{\log\log n}{\log n}\right)\right)\\ &=\ln\ln n+\ln 2-\ln c+O\left(\frac{\log\log n}{\log n}\right) \end{align} Finally, we have \begin{align} r&=\frac{2\ln n}c-\frac{2\ln\ln n}c-\frac{2\ln 2}c+\frac{2\ln c}c+\frac 2c+1+O\left(\frac{\log\log n}{\log n}\right)\\ &=2\log_b c-2\log_b\log_b c+2\log_b\frac e2+1+O\left(\frac{\log\log n}{\log n}\right) \end{align}