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

  • $\begingroup$ 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. $\endgroup$ – Graphth Nov 14 '11 at 2:47
  • $\begingroup$ @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? $\endgroup$ – Srivatsan Nov 14 '11 at 2:49
  • $\begingroup$ 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. $\endgroup$ – Graphth Nov 14 '11 at 2:51
  • $\begingroup$ 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. $\endgroup$ – Graphth Nov 14 '11 at 2:53
  • $\begingroup$ @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. $\endgroup$ – Srivatsan Nov 14 '11 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.