3
$\begingroup$

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

1 Answers 1

2

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

  • 0
    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.2011-11-14
  • 0
    @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?2011-11-14
  • 0
    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.2011-11-14
  • 0
    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.2011-11-14
  • 0
    @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.2011-11-14
  • 0
    I have looked over your proof and I still think maybe there is a slight error, but one that is easily fixed. Right at the end, as $n \to \infty$, $L^{k/n} \to 1$. So, we can not say that if $n$ is sufficiently large, then $L^{k/n} \geq 1 + \epsilon$... because as $n$ gets bigger and bigger, $L^{k/n}$ actually becomes less than $1 + \epsilon$ for any $\epsilon$. Or I am just confused?2011-11-14
  • 0
    But, I think there is an easy fix. Just take the limit as $n$ goes to $\infty$ of both sides. The right hand side goes to $L - \epsilon$. Thus, $\lim_{n \to \infty} (\alpha_n)^{1/n} \geq L - \epsilon$ for every $\epsilon > 0$, so $\lim_{n \to \infty} (\alpha_n)^{1/n} \geq L$. Adding in the fact that the limit must be bounded above by $L$ based on the supremum, we see that the limit must be $L$.2011-11-14
  • 0
    @Graphth You are correct. That should read "at most 1+epsilon". The basic idea is that the denominator goes to $1$ as $n \to \infty$. Thanks for the catch! (Or alternatively, as you point out, you can take the limit as $n \to \infty$ as well.)2011-11-14
  • 0
    And, lastly, I want to say thank you for all your help. And, you are exactly correct that I was thinking $\alpha_n = \alpha(G^n)^{1/n}$ at first.2011-11-14