MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
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|}$. – Tobias Fritz Nov 27 '12 at 1:35

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.

share|cite|improve this answer
Two great answers, I am sorry I can not accept them both. Thanks for your help. – Graphth Dec 1 '12 at 17:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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