In the paper "On Multi-dimensional Packing Problems" by Chekuri and Khanna there is the following lemma:

Lemma 4.3.(p. 191 of the paper) Let $G$ be a graph on $n$ vertices with $\omega(G) ≤ k$. Then $\alpha(G) ≥ n^{1/k}$.

If we substitute $G$ by a complete graph, then we get: $\omega(G) = n$, then $\alpha(G) ≥ n^{1/n}>1$.

However, if I correctly understand the notion of an independence number, then $\alpha(K_n)=1,\forall n$. A contradiction to the lemma.

I have checked for several cases and it seems that this is the only one where the lemma doesn't hold.

Could someone explain what is wrong with my reasoning?

P.S. I sent this question to one of the authors before posting it here, but haven't received any answer.


1 Answer 1


Where it says

then any maximal independent set has size at least $n^{1/k}$,

it should say

then any maximal independent set has size at least the floor of $n^{1/k}$,

(Then this sentence is true for the complete graph $K_k$.)

They are being a bit sloppy, but I imagine that they just need the result for "large enough $n$".

  • 1
    $\begingroup$ No problem! It was fun finding the "mistake" :) Just add "for large enough $n$" to the statement, and things are fine. $\endgroup$
    – Emil
    Commented Nov 1, 2010 at 14:54
  • $\begingroup$ However, for large enough $n$ the lemma still doesn't hold for $K_k$. $\endgroup$ Commented Nov 1, 2010 at 15:20
  • 1
    $\begingroup$ @Oleksandr, for any fixed $k$, the statement of the lemma holds for large enough $n$. $\endgroup$
    – Emil
    Commented Nov 1, 2010 at 16:29
  • $\begingroup$ Preciseness is a good explanation. You are right! $\endgroup$ Commented Nov 1, 2010 at 16:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.