2
$\begingroup$

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!

  • 0
    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)$.2012-07-15

1 Answers 1

2

Firstly, we have $0. 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, 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}

  • 0
    @Walkland Some books are suggested. Graham, Knuth, Patashnik: *Concrete Mathematics*; Don Knuth: *The Art of Com$p$uter Programming*. All the techniques used here are well-introduced in *Concrete Mathematics*.2012-07-18