Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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}

share|improve this answer
    
Thank you Frank! –  Walkland Jul 17 '12 at 19:59
    
@Walkland Some books are suggested. Graham, Knuth, Patashnik: Concrete Mathematics; Don Knuth: The Art of Computer Programming. All the techniques used here are well-introduced in Concrete Mathematics. –  Frank Science Jul 18 '12 at 0:57

Your Answer

 
discard

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.