# Lower bound on independence number in terms of clique number and order of graph

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

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