<p>It is a standard fact that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$ for every graph $G$. (See the proof below.)
Denoting $b_k := \sqrt[k]{\alpha(G^k)}$, this implies that the tail of the sequence $(b_k)_{k \geq 1}$ cannot be monotone decreasing, and hence there are infinitely many $k$'s for which $b_{k+1} \geq b_k$, as required.</p>

<hr>

<p>In order to prove that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$ note that the sequence $(\alpha(G^k))_{k \geq 1}$ is super multiplicative, i.e., $\alpha(G^{k+\ell}) \geq \alpha(G^k) \alpha(G^\ell)$ for all $k,\ell \geq 1$. Indeed, if $I$ is an independent set in $G^k$, and $J$ is an independent set in $G^\ell$, then $I \times J$ is an independent set in $G^{k+\ell}$. Therefore, by (the multiplicative version of) <a href="http://en.wikipedia.org/wiki/Superadditivity" rel="nofollow">Fekete's lemma</a> it follows that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$.</p>

CC BY-SA 3.0
2013-08-11T15:33:09.007Z
2013-08-11T15:33:09.007Z
Igor Shinkar
<p>Let $\alpha(C_{n}^{\boxtimes k})$ be independence number of $k$-fold strong product of an $n$-vertex cycle graph $C_{n}$.</p>

<p>$\forall n &gt; 6$, is $\alpha(C_{n}^{\boxtimes (k+r)})^{\frac{1}{k+r}} \geq \alpha(C_{n}^{\boxtimes k})^{\frac{1}{k}}$ for infinitely many positive integer pairs $(k,r)$?</p>

CC BY-SA 3.0
2013-08-11T14:17:06.453Z
Doesn't it follows directly from super-multiplicativity of $\alpha(C_n^k)^{1/k}$? Just take any $k$ and $r=1$.
Igor Shinkar
CC BY-SA 3.0
2013-08-11T15:23:08.780Z
Sorry, i think my previous comment is incorrect. I meant that the sequence $(\alpha(G^k))_{k \geq 1}$ is super-multiplicative.
Igor Shinkar
CC BY-SA 3.0
2013-08-11T15:35:19.130Z
So $\alpha(G^{2k}) \geq \alpha(G^{k})\alpha(G^{k}) \implies \alpha(G^{2k})^{\frac{1}{2k}} \geq \alpha(G^{k})^\frac{1}{k}$ and we can take $r=k$? Is there a reference for supermultiplicativity?
Turbo
CC BY-SA 3.0
2013-08-11T15:40:28.717Z
Right, your example is much easier.
The super-multiplicativity is just by taking product of the maximal independent sets on the RHS.
Igor Shinkar
<graph-theory><it.information-theory>
On the Shannon Capacity of Cycles
Turbo
# On the Shannon Capacity of Cycles

(Asked by: username_0 on 2013-08-11)

Let $\alpha(C\_{n}^{\boxtimes k})$ be independence number of $k$-fold strong product of an $n$-vertex cycle graph $C\_{n}$.

$\forall n > 6$, is $\alpha(C\_{n}^{\boxtimes (k+r)})^{\frac{1}{k+r}} \geq \alpha(C\_{n}^{\boxtimes k})^{\frac{1}{k}}$ for infinitely many positive integer pairs $(k,r)$?

**Tags:** graph-theory, it.information-theory
> **Comments:**
> **username_1**: Doesn't it follows directly from super-multiplicativity of $\alpha(C_n^k)^{1/k}$? Just take any $k$ and $r=1$.  
> **username_1**: Sorry, i think my previous comment is incorrect. I meant that the sequence $(\alpha(G^k))_{k \geq 1}$ is super-multiplicative.  
> **username_0**: So $\alpha(G^{2k}) \geq \alpha(G^{k})\alpha(G^{k}) \implies \alpha(G^{2k})^{\frac{1}{2k}} \geq \alpha(G^{k})^\frac{1}{k}$ and we can take $r=k$? Is there a reference for supermultiplicativity?  
> **username_1**: Right, your example is much easier. The super-multiplicativity is just by taking product of the maximal independent sets on the RHS.  

---

## 1 answers

### Answer by username_1 on 2013-08-11. Score: 4 | Accepted answer

It is a standard fact that $\lim\_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup\_{k \to \infty} \sqrt[k]{\alpha(G^k)}$ for every graph $G$. (See the proof below.)
Denoting $b\_k := \sqrt[k]{\alpha(G^k)}$, this implies that the tail of the sequence $(b\_k)\_{k \geq 1}$ cannot be monotone decreasing, and hence there are infinitely many $k$'s for which $b\_{k+1} \geq b\_k$, as required.

---

In order to prove that $\lim\_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup\_{k \to \infty} \sqrt[k]{\alpha(G^k)}$ note that the sequence $(\alpha(G^k))\_{k \geq 1}$ is super multiplicative, i.e., $\alpha(G^{k+\ell}) \geq \alpha(G^k) \alpha(G^\ell)$ for all $k,\ell \geq 1$. Indeed, if $I$ is an independent set in $G^k$, and $J$ is an independent set in $G^\ell$, then $I \times J$ is an independent set in $G^{k+\ell}$. Therefore, by (the multiplicative version of) [Fekete's lemma](http://en.wikipedia.org/wiki/Superadditivity) it follows that $\lim\_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup\_{k \to \infty} \sqrt[k]{\alpha(G^k)}$.


---

