1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ (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 :) $\endgroup$ Commented Oct 23, 2018 at 7:23

2 Answers 2

0
$\begingroup$

I guess your answer is correct. Still, I think we can make it much shorter without using Stirling's approximation (please point out if there are errors).
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)$

$\endgroup$
1
  • $\begingroup$ Looks correct to me. Thank you for your answer. $\endgroup$
    – Ira Re
    Commented Oct 24, 2018 at 14:42
0
$\begingroup$

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*}

$\endgroup$
2
  • $\begingroup$ Or can you see any errors? $\endgroup$
    – Ira Re
    Commented Dec 4, 2016 at 12:34
  • $\begingroup$ 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)} $$ $\endgroup$ Commented Oct 30, 2018 at 3:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .