0
$\begingroup$

This is my first ever post so I hope this is an appropriate question.

Basically I am looking at the paper here: http://homepages.math.uic.edu/~mubayi/papers/biclique.pdf Namely theorem 5.

Now, feel free to read it of course but to summerise the salient details to ask my question:

We are colouring a graph $G$. The colour classes are sequences with each entry of the sequence a term in $\{1, \dots, m\}$. Note that different colour classes may have different lengths. Now, the paper doesn't worry about $\log m$ being an integer, but I think in context of what the colouring is doing I think it has to be. Anyway, the paper reasons that "the maximum length colour sequence is length log(m)". I reason "for $m$ of the form $m=2^n -1$, the maximum length colour sequence is length $\lceil \log_{2}m \rceil$. For any other $m$, the maaximum length colour sequence is length $\lfloor \log_{2}m \rfloor$. Now, the paper that concludes that $\chi(G) \le m^{\log_{2}m}(1+o(1))$. It's also worth noting that this is for $\chi(G)$ large and $m$ grows with $\chi(G)$.

Is the paper correct to conclude how it does? Don't we have to say that $\chi(G) \le m^{\lceil \log_{2}m \rceil}(1+o(1))$? Or is this the same thing?

Any help appreciated and again I hope this is the correct place to ask this sort of question.

$\endgroup$
2
  • $\begingroup$ $m^{\lceil \log_2 m\rceil}$ and $m^{\log_2 m}$ have a different rate of growth so having the first as an upper bound doesn't imply that the second is an upper bound. But I haven't studied the paper so I won't give an opinion on it. You should address questions like this to the author in the first instance. $\endgroup$ Jul 28, 2014 at 11:46
  • $\begingroup$ Of course, I did try to but he's quite busy at the moment. $\endgroup$
    – Shaun
    Jul 28, 2014 at 12:04

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.