On the Shannon Capacity of Cycles

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)$?

• Doesn't it follows directly from super-multiplicativity of $\alpha(C_n^k)^{1/k}$? Just take any $k$ and $r=1$. – Igor Shinkar Aug 11 '13 at 14:17
• Sorry, i think my previous comment is incorrect. I meant that the sequence $(\alpha(G^k))_{k \geq 1}$ is super-multiplicative. – Igor Shinkar Aug 11 '13 at 15:23
• 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? – 1.. Aug 11 '13 at 15:35
• Right, your example is much easier. The super-multiplicativity is just by taking product of the maximal independent sets on the RHS. – Igor Shinkar Aug 11 '13 at 15:40

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 it follows that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$.