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.


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$".

| cite | improve this answer | |
  • 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 Nov 1 '10 at 14:54
  • $\begingroup$ However, for large enough $n$ the lemma still doesn't hold for $K_k$. $\endgroup$ – Oleksandr Bondarenko Nov 1 '10 at 15:20
  • 1
    $\begingroup$ @Oleksandr, for any fixed $k$, the statement of the lemma holds for large enough $n$. $\endgroup$ – Emil Nov 1 '10 at 16:29
  • $\begingroup$ Preciseness is a good explanation. You are right! $\endgroup$ – Oleksandr Bondarenko Nov 1 '10 at 16:37

Your Answer

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

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