Upper bound on Shannon capacity based on independence number - MathOverflow

Upper bound on Shannon capacity based on independence number

2012-11-26T22:03:07Z

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

Answer by Andrew D. King for Upper bound on Shannon capacity based on independence number

2012-11-26T23:01:48Z

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

Answer by Tobias Fritz for Upper bound on Shannon capacity based on independence number

2012-11-26T23:51:33Z

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.