# Shannon capacity definition

I have seen the Shannon capacity defined in two ways:

$\Theta(G) = \sup_k \sqrt[k]{\alpha(G^k)}$

$\Theta(G) = \lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}$

My question is, basically, how do we know the limit (in the bottom one) exists, and how do we know the two definitions are equal?

$G^k$, by the way, stands for the strong product of $k$ copies of $G$.

I do know that $\alpha(G \boxtimes H) \geq \alpha(G) \cdot \alpha(H)$. To see this, let $I_G$, $I_H$ be independent sets in $G$ and $H$. Then, $I_G \times I_H$ is independent in $G \boxtimes H$. At first, I mistakenly decided this meant the sequence $\sqrt[k]{\alpha(G^k)}$ must be nondecreasing. From this, I made sense that the supremum and limit are the same. Since an upper bound is $\chi(\bar{G})$, the limit definition exists. But, this was a bad assumption. I have discovered, using Sage, that

$\alpha(C_5) = 2$

$\sqrt{\alpha(C_5^2)} = \sqrt{5}$

$\sqrt[3]{\alpha(C_5^3)} = \sqrt[3]{10}$

And, $\sqrt{5} > \sqrt[3]{10}$.

Without loss of generality, assume that the graph is not complete. Let $\alpha_n := \alpha(G^n)$; we need the following facts (noted by the OP in the question):

1. $\alpha_n$ is montononically increasing.
2. $\alpha_n \geqslant 2$.
3. $\alpha_{n+m} \geqslant \alpha_n \alpha_m$.
4. $\alpha_{nm} \geqslant \alpha_n^m$. (This is a corollary of item (3).)
5. $\alpha_n \geqslant \alpha_1^n \geqslant 2^n$.

Let $L$ be the supremum of $\alpha_n^{1/n}$ for all $n$. From (5.), it is clear that $L \geqslant 2$. We want to prove that $\alpha_n^{1/n}$ approaches $L$ as $n \to \infty$.

Fix any $\varepsilon \in (0,1)$. Then there exists $k \in \mathbb N$ such that $\alpha_k \geqslant (L - \varepsilon)^k$. Now, for any $n$, define $q := \lfloor n/k \rfloor$. Then we have the following chain of inequalities: $$\begin{eqnarray*} \alpha_n &\geqslant& \alpha_{kq} \\ &\geqslant& \alpha_k^q \\ &\geqslant& (L - \varepsilon)^{kq} \\ &\stackrel{(*)}{\geqslant}& (L - \varepsilon)^{n - k} \\ &\geqslant& \frac{(L - \varepsilon)^n}{L^{k}} \end{eqnarray*}$$ As an exercise, justify the above steps carefully. [[The following facts are helpful to show $(\ast)$: (i) $kq \geqslant n - k + 1 \geqslant n - k$; and (ii) $L - \varepsilon \geqslant 2 - 1 = 1$.]]

From the chain of inequalities, we can conclude that $$\alpha_n^{1/n} \geqslant \frac{L - \varepsilon}{L^{k/n}}.$$ Now, taking $n$ sufficiently large, we can make the denominator at most, say, $1 + \varepsilon$. That is, there exists some $N$ such that for all $n \geqslant N$, we have $\alpha_n^{1/n} \geqslant \frac{L - \varepsilon}{1 + \varepsilon}$. Since $\varepsilon > 0$ is arbitrary, it follows that $\alpha_n^{1/n} \to L$ as $n \to \infty$.

• I thank you for the reply. But, I am seeing a few errors. I think you misunderstood some of the things I was saying. $\alpha_{n+m}$ is not necessarily $\alpha_n \alpha_m$. For example, take $n=m=1$ and look at the $C_5$ example above. $\alpha_n$ can be 1 in general. In the specific $C_5$ example, yes, $\geq 2$ but I'm asking in general for any graph. – Graphth Nov 14 '11 at 2:47
• @Graphth Apologies. It is indeed not the case that $\alpha_{n+m} = \alpha_n \alpha_m$. What is true (and what I do need in my answer) is that $\alpha_{n+m} \geqslant \alpha_n \alpha_m$. I will edit my answer accordingly. EDIT: Is the answer with the modification ok? – Srivatsan Nov 14 '11 at 2:49
• Hopefully you noticed I just edited my comment as one thing I said was incorrect. I have corrected my comment and I think it should be fine now. – Graphth Nov 14 '11 at 2:51
• Yes, I agree $\alpha_{n+m} \geq \alpha_n \alpha_m$. I actually must go right now but I will check this answer in the morning. Thank you for your help. – Graphth Nov 14 '11 at 2:53
• @Graphth One clarification w.r.t. notation. $\alpha_n$ is $\alpha(G^n)$ and not $\alpha(G^n)^{1/n}$. While it is true that $\alpha(G^n)^{1/n}$ is not necessarily increasing, the sequence $\alpha(G^n) = \alpha_n$ is monotonically increasing as assumed by the answer. – Srivatsan Nov 14 '11 at 2:57