<p>Where it says</p>

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

<p>it should say</p>

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

<p>(Then this sentence is true for the complete graph $K_k$.)</p>

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

CC BY-SA 2.5
2010-11-01T14:54:28.970Z
No problem! It was fun finding the "mistake" :) Just add "for large enough $n$" to the statement, and things are fine.
Emil
CC BY-SA 2.5
2010-11-01T15:20:33.473Z
However, for large enough $n$ the lemma still doesn't hold for $K_k$.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-11-01T16:29:10.100Z
@Oleksandr, for any fixed $k$, the statement of the lemma holds for large enough $n$.
Emil
CC BY-SA 2.5
2010-11-01T16:37:58.287Z
Preciseness is a good explanation. You are right!
Oleksandr Bondarenko
CC BY-SA 2.5
2010-11-01T14:46:52.317Z
2010-11-01T14:46:52.317Z
Emil
<p>In the paper "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.6877&amp;rep=rep1&amp;type=pdf" rel="nofollow">On Multi-dimensional Packing Problems</a>" by Chekuri and Khanna there is the following lemma:</p>

<p>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}$.</p>

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

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

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

<p>Could someone explain what is wrong with my reasoning?</p>

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

<graph-theory><co.combinatorics>
Lower bound on independence number in terms of clique number and order of graph
Oleksandr Bondarenko
# Lower bound on independence number in terms of clique number and order of graph

(Asked by: username_0 on 2010-11-01)

In the paper "[On Multi-dimensional Packing Problems](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.6877&rep=rep1&type=pdf)" 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.

**Tags:** graph-theory, co.combinatorics


---

## 1 answers

### Answer by username_1 on 2010-11-01. Score: 7 | Accepted 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$".

> **Comments:**
> **username_1**: No problem! It was fun finding the "mistake" :) Just add "for large enough $n$" to the statement, and things are fine.  
> **username_0**: However, for large enough $n$ the lemma still doesn't hold for $K_k$.  
> **username_1**: @Oleksandr, for any fixed $k$, the statement of the lemma holds for large enough $n$.  
> **username_0**: Preciseness is a good explanation. You are right!  

---

