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