Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For $G$ a graph, let $\alpha(G)$ be its independence number and $\Theta(G)=\lim_n \sqrt[n]{\alpha(G^{\boxtimes})}$ its Shannon capacity, where $\boxtimes$ denotes strong product.

Consider graphs $G$ and $H$ satisfying $\alpha(G)=\Theta(G)$ and $\alpha(H)=\Theta(H)$. For example, $G$ and $H$ could be perfect, but the more interesting situations arise when neither of them is perfect.

Question: Does this assumption imply
(1) $\alpha(G\boxtimes H) = \alpha(G)\alpha(H)$ ?
(2) $\Theta(G\boxtimes H) = \Theta(G)\Theta(H)$ ?
(3) $\Theta(G + H) = \Theta(G) + \Theta(H)$ ?

Here, $G+H$ stands for the disjoint union of $G$ and $H$.

If my reasoning is correct, then (1) and (2) are equivalent and imply (3).

As far as I can see, neither the work of Haemers nor the results of Alon have anything directly to say about these questions. But then again, I am not an expert on this, so I might have missed something obvious.

Edit (see Will Traves' answer): Actually, I am specifically interested in those $G$ and $H$ which are well-covered.

Edit: The paper is here.

share|improve this question
So, have you ever answered any of your above questions? I am interested in all 3 separately. –  Graphth Dec 8 '12 at 16:32
One can also ask whether $\alpha(G)=\Theta(G)$ implies $\alpha(G)=\vartheta(G)$; if this is true, then the other conjectures immediately follow from the basic properties of the Lovász number $\vartheta$. Alas, we haven't been able to answer any of these four questions yet; but since our work lies mainly in relating these questions to problems in the mathematical foundations of quantum mechanics, we also haven't tried really hard. Our paper should be on the arXiv within a few days; I will announce it here. –  Tobias Fritz Dec 8 '12 at 17:32
$\alpha(G) = \Theta(G)$ does not imply $\alpha(G) = \vartheta(G)$. Haemers gives a counterexample in "An Upper Bound for the Shannon Capacity of a Graph". –  Graphth Dec 10 '12 at 18:46
By the way, did you know that if you do @Graphth before your response, then it will notify me of a response? I think since you wrote the question that it will notify you when I respond, even if I don't do @tobias –  Graphth Dec 10 '12 at 18:47
@Graphth: thanks a bunch, that's very helpful! We didn't know about that paper of Haemers. It will take us some time now to revise our paper now that we have this new information. Leave me a PM if we can use your real name in the acknowledgments. –  Tobias Fritz Dec 12 '12 at 18:22

3 Answers 3

up vote 4 down vote accepted

By now, we have been able to resolve this question, and our revised paper contains a proof showing that the answer to all three questions is negative in a very strong sense. Let me provide a brief summary here and refer to the paper for more details.

What we show is this: there exist graphs $G$ and $H$ with $\alpha(G)=\Theta(G)$ and $\alpha(H)=\vartheta(H)$ which violate all three desired inequalities. Note that the property $\alpha(H)=\vartheta(H)$ is even stronger than the required property $\alpha(H)=\Theta(H)$.

The construction crucially relies on the definitions and results on hypergraphs discussed in our paper and on results of Haemers. We have partially translated it into pure graph-theoretic terms, but it does not seem possible to do so completely.

The counterexample turns out to be the following:

  • $G$ is a $108$-regular graph on $220$ vertices. The vertices correspond to the $3$-element subsets of $\{1,\ldots,12\}$ and two such vertices are adjacent whenever the subsets intersect in exactly one element. This graph was considered by Haemers, who showed that $\alpha(G) = \Theta(G) < \vartheta(G)$, and this property is the most important ingredient for us.

  • $H$ is a graph constructed from the complement of $G$ which turns out to have $1131460$ vertices.

I suspect that a similar construction can be carried out starting with any graph $G$ having the property that $\alpha(G) = \Theta(G) < \vartheta(G)$, but we haven't checked all the details of this.

share|improve this answer
Isn't $G$ 108-regular? $\{10,11,12\}$ is adjacent to $3\cdot\binom92$ 3-sets. (that's also what your paper says. :) –  Wolfgang Feb 2 at 16:48
@Wolfgang: yes, that's exactly right! And that is relevant for the proof of our Theorem 7.4.3, on which our results are based. Hence my last sentence: it's probably possible to use a similar construction for any $G$ with $\alpha(G)=\Theta(G)<\vartheta(G)$, but the details are not clear. –  Tobias Fritz Feb 2 at 18:01
so why don't you edit that in your answer? –  Wolfgang Feb 3 at 8:34
@Wolfgang: whoops, I hadn't realized that you were pointing out a typo! Thanks, corrected. –  Tobias Fritz Feb 3 at 11:18

@Tobias: Sorry that my answer was not clear. According to Plummer http://www.dtic.mil/dtic/tr/fulltext/u2/a247861.pdf there are two equivalent definitions of well-covered graphs, one in terms of vertex covers and one in terms of independent sets.

A set of vertices $S$ is called a vertex cover if every vertex is either in $S$ or is adjacent to a vertex in $S$. The set $S$ is a minimum vertex cover if it is a vertex cover and no proper subset is a vertex cover. A set of vertices $T$ is called an independent set if no two vertices in $T$ are connected by an edge of the graph. A maximal independent set is one in which each vertex outside of $T$ is adjacent to some vertex in $T$. Note that if $V$ is the set of all vertices in the graph then $T$ is a maximal independent set if and only if $V \setminus T$ is a minimum vertex cover.

A graph is well-covered if all maximal independent sets have the same cardinality. Equivalently, a graph is well-covered if all minimum vertex covers have the same cardinality.

Of course, if $\bar{G}$ is the complementary graph to $G$ then a set of vertices forms a maximal clique in $\bar{G}$ precisely when the same set of vertices forms an independent set in $G$. So your condition that the "complements satisfy the additional property that all maximal cliques have the same size" means that the graphs themselves are well-covered. I don't see need for the additional requirement that every edge appears in some maximal clique - it seems to me that this always occurs.

You might find the paper by Philip Matchett helpful. It's emphasis is slightly different but it deals with operations on well-covered graphs. It can be found here: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r45.

share|improve this answer
Ok, now I get it, thanks! That perfectly answers my side question. –  Tobias Fritz Oct 5 '12 at 16:48

I believe that graphs in which all maximal cliques have the same size and every edge is contained in a maximal clique are called well-covered graphs. Sorry that I can't shed light on any of the serious questions that you raise.

share|improve this answer

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.