1
$\begingroup$

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

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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|}$. $\endgroup$ Nov 27, 2012 at 1:35
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Two great answers, I am sorry I can not accept them both. Thanks for your help. $\endgroup$
    – GeoffDS
    Dec 1, 2012 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.