I am reading Tau and Vu's book Additive Combinatorics, and I came across a step in a proof that I am not able to verify.

On page 252, in the last line of the proof of Theorem 6.4, it is stated that the following inequality holds for all integers $m \geq 1$ and $d \geq 16$:

$\frac{d}{2^m + 1} + \frac{m}{2}\frac{2^m}{2^m+1} \geq \frac{\log_2 d}{4}$

I would appreciate a proof of this fact. I have tried various ways of rearranging the inequality, and I have tried fixing one variable and then taking the derivative with respect to the other, but I'm not sure if this will work. Any help would be appreciated.

Note: As I state in the comments below, we may assume $m \leq d$. I'm not sure if this is necessary though.

The result in the book is cited to be in a paper by Shearer, which I've found here: https://www.sciencedirect.com/science/article/pii/0012365X8390273X, But I can't find this result in this paper. Am I just missing it?

  • $\begingroup$ What are $m,d$? $\endgroup$ – Jair Taylor Jun 10 at 22:57
  • $\begingroup$ Hi sorry - they are integers. $\endgroup$ – Tanny Libman Jun 10 at 23:27
  • $\begingroup$ They have no graph-theoretic meaning? $\endgroup$ – Jair Taylor Jun 10 at 23:33
  • 1
    $\begingroup$ $d$ is the max degree in a graph and $m$ is a subset of the set of neighbors of some vertex, so indeed $m \leq d$ and this may be helpful! $\endgroup$ – Tanny Libman Jun 11 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.