# n >= (k-2)! implies k = O(log n / log log n)?

Let n and k be some integers. k > 3. Let $n \geq (k-2)!$.

I have to show, that $k = \mathcal O\left(\frac{\log{n}}{\log{\log{n}}}\right)$

This statement was used in the article On vertex rankings of graphs and its relatives by I.Karpas et. al. I have to verify it for my bachelor project. The statement was marked as "easy to see" in the article.

By using Stirling's approximation one can show that \begin{equation*} \begin{split} \log{n} & \geq \log{\left(k-2\right)!}\\ & \geq \log{\sqrt{2\pi}} + \left(k-\frac{3}{2}\right)\log{\left(k-2\right)} - \left(k-2\right)\log{e}\\ & \geq \left(k-2\right)\log{\left(k-2\right)} - \left(k-2\right)\log{e}\\ & = \left(k-2\right)\left(\log{\left(k-2\right)} - \log{e}\right)\ \end{split} \end{equation*}

That's actually all I could find out till now. I was also trying to assume that $k \neq \mathcal O\left(\frac{\log{n}}{\log{\log{n}}}\right)$ and to show that $k > c\cdot\frac{\log{n}}{\log{\log{n}}}$ for all $c>0$ would lead to contradiction.

Other possibility would be to show that, there exists $c>0$ such that $$\frac{\log{n}}{\log{\log{n}}} \geq \frac{\log{(k-2)!}}{\log{\log{(k-2)!}}} \geq\ldots\geq c\cdot k$$

Unfortunately I fail on both approaches.

My question: Do you have any idea how to properly estimate the statements above or any other approaches to conclude the main statement?

• (soft comment) I think there is a slight error in that paper in section 3.1 (in the def. of $p_i(T,r)$ ). I think that is a typo and there are two more mistakes in that section (both of minor nature). Let me know if I am wrong. After those three small corrections, the proof is correct (in my knowledge). If you are struggling with it (upperbound), let me know. I am also reading that paper :) Commented Oct 23, 2018 at 7:23

Let $$m=k-2$$
We have $$\log m!=\Theta(m\log m)$$.
Hence there are positive constants $$a,b$$ such that $$a~x\log x\leq \log x!\leq b~x\log x$$ $$\frac{\log n}{\log\log n}\geq \frac{\log m!}{\log \log m!}\geq \frac{am\log m}{\log(bm\log m)}=a\frac{m\log m}{\log b+\log m+\log \log m}$$ Therefore, $$m\leq \frac{1}{a}\frac{\log b+\log m+\log \log m}{\log m}\frac{\log n}{\log \log n}\leq c \frac{\log n}{\log \log n}$$ where $$c$$ is a positive constant (eg:$$c=3/a$$) assuming $$m\geq b$$. Hence $$m=O(\log n/\log \log n)$$
Let $m=k-2$ \begin{equation*} \begin{split} \frac{\log{n}}{\log{\log{n}}} & \geq \frac{\log{m!}}{\log{\log{m!}}} \\ & \approx \frac{\log{\left(m^{m}\cdot e^{-m}\sqrt{2\pi\cdot m}\right)}}{\log{\left(\log{\left(m^{m}\cdot e^{-m}\sqrt{2\pi\cdot m}\right)}\right)}} \\ & = \frac{m\log{m} - m\log{e} + \frac{1}{2}\log{2\pi} + \frac{1}{2}\log{m}}{\log{\left(m\log{m} - m\log{e} + \frac{1}{2}\log{2\pi} + \frac{1}{2}\log{m}\right)}} \\ & = \frac{\left(m+\frac{1}{2}\right)\log{m} \overbrace{- m + \frac{1}{2}\log{2\pi}}^{\leq 0\text{ for } m > \frac{1}{2}\log{2\pi}}}{\log{\left(m\log{m} \underbrace{- m + \frac{1}{2}\log{2\pi} + \frac{1}{2}\log{m}}_{\leq m\log{m}}\right)}} \\ & \geq \frac{\left(m+\frac{1}{2}\right)\log{m}}{\log{\left(2m\log{m}\right)}} \\ & = \frac{\left(m+\frac{1}{2}\right)\log{m}}{\log{m} + \log{\left(2\log{m}\right)}} \\ & = \frac{\left(m+\frac{1}{2}\right)}{1 + \frac{\log{\left(2\log{m}\right)}}{\log{m}}} \\ & \geq \frac{m}{2} \\ & = \frac{k-2}{2} \end{split} \end{equation*}
• Oh, I think there is a small one in substituting $-m+\frac{1}{2}\log 2\pi$. This term is $\leq 0$ for $m>\frac{1}{2}\log 2\pi$ but after substitution, you write $\geq$. You can only write $$\frac{\log n}{\log \log n}=\frac{(m+\frac{1}{2})\log m-m+\frac{1}{2}\log 2\pi}{\log(m\log m-m+\frac{1}{2}\log 2\pi+\frac{1}{2}\log m)}\leq \frac{(m+\frac{1}{2})\log m}{\log(m\log m-m+\frac{1}{2}\log 2\pi+\frac{1}{2}\log m)}$$ Commented Oct 30, 2018 at 3:56