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