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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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

Improve this answer
$\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$ Commented 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.

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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.