Upper bound on Shannon capacity based on independence number - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T22:35:15Z http://mathoverflow.net/feeds/question/114589 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114589/upper-bound-on-shannon-capacity-based-on-independence-number Upper bound on Shannon capacity based on independence number Graphth 2012-11-26T22:03:07Z 2012-11-26T23:51:33Z <p>The Shannon capacity of a graph is defined as $$\Theta(G) = \sup_k \sqrt[k]{\alpha(G^k)}.$$</p> <p>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$.</p> http://mathoverflow.net/questions/114589/upper-bound-on-shannon-capacity-based-on-independence-number/114602#114602 Answer by Andrew D. King for Upper bound on Shannon capacity based on independence number Andrew D. King 2012-11-26T23:01:48Z 2012-11-26T23:01:48Z <p>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.</p> <p>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.</p> <p><a href="http://www.research.ibm.com/people/s/shearer/indpal.html" rel="nofollow">http://www.research.ibm.com/people/s/shearer/indpal.html</a></p> <p><a href="http://mathworld.wolfram.com/PaleyGraph.html" rel="nofollow">http://mathworld.wolfram.com/PaleyGraph.html</a></p> <p><a href="http://mathworld.wolfram.com/ShannonCapacity.html" rel="nofollow">http://mathworld.wolfram.com/ShannonCapacity.html</a></p> http://mathoverflow.net/questions/114589/upper-bound-on-shannon-capacity-based-on-independence-number/114608#114608 Answer by Tobias Fritz for Upper bound on Shannon capacity based on independence number Tobias Fritz 2012-11-26T23:51:33Z 2012-11-26T23:51:33Z <p>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.</p> <p><a href="http://arxiv.org/abs/cs/0608021" rel="nofollow">This paper</a> 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.</p>