# Upper bound on Shannon capacity based on independence number

The Shannon capacity of a graph is defined as $$\Theta(G) = \sup_k \sqrt[k]{\alpha(G^k)}.$$

So, $\alpha(G) \leq \Theta(G)$ but $\Theta(G)$ can be strictly greater than $\alpha(G)$. I am wondering if there is any upper bound based on the independence number itself? Specifically, are there graphs where $\Theta(G) \geq \alpha(G) + 1$? It seems like the structure of the strong product limits how much the independence number can grow. The independence number would have to grow pretty quick just for $\sqrt[k]{\alpha(G^k)}$ to get up to $\alpha(G) + 1$ for some $k$.

-

Self-complementary vertex-transitive graphs have Shannon capacity $\sqrt n$, so if this number is far from $\alpha$, then you have what you're looking for.

Paley graphs have this property, and as you can see here, there are examples for which $\alpha$ is indeed much less than the Shannon capacity.

http://www.research.ibm.com/people/s/shearer/indpal.html

http://mathworld.wolfram.com/PaleyGraph.html

http://mathworld.wolfram.com/ShannonCapacity.html

-
You don't actually need vertex-transitivity: if $G$ is self-complementary via some isomorphism $\phi:G\to\overline{G}$, then $\{(v,\phi(v))|v\in G\}$ is an independent set in $G\cdot\overline{G}$ with cardinality $|G|$, the number of vertices of $G$. Hence $\Theta(G)\geq\sqrt{|G|}$. –  Tobias Fritz Nov 27 '12 at 1:35

An inequality as simple as $\Theta(G)\leq \alpha(G)+1$ can certainly not hold for all $G$: take some $G$ with $\Theta(G)>\alpha(G)$ and consider the disjoint union $G+G$. Since $\alpha$ is additive under disjoint union while $\Theta$ is superadditive, this $G+G$ will have a gap between $\Theta$ and $\alpha$ which is at least twice as big as $G$'s. Now repeat this process if necessary.

This paper of Alon and Lubetzky seems highly relevant. After proving several negative results (which I don't fully grasp), they conjecture that $$\Theta(G) \leq 2\max_{k=1,\ldots,|G|} \sqrt[k]{\alpha(G^k)} ,$$ where $|G|$ is the number of vertices.

-
Two great answers, I am sorry I can not accept them both. Thanks for your help. –  Graphth Dec 1 '12 at 17:06