Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

August 10, 2013

The Shannon Capacity of a Graph, 1

Posted by Tom Leinster

You’ve probably had the experience where you spell your name or address down the phone, and the person on the other end mistakes one letter for another that sounds similar: P sounds like B, which is easily mistaken for V, and so on. Under those circumstances, how can one most efficiently communicate without risk of error?

Five-cycle with vertices labelled P, B, V, D, T

Shannon found the answer, but this isn’t part of his most famous work on communication down a noisy channel. There, the alphabet has no structure: any substitution of letters is as likely as any other. Here, the alphabet has the structure of a graph.

Today, I’ll explain Shannon’s answer. Next time, I’ll explain how it’s connected to the concept of maximum diversity, and thereby to magnitude.

First, let’s work through the example shown. We have some message that we want to communicate down the phone, and for some reason, we have to encode it using just the letters P, B, V, D and T. But P could be confused with B, B with V, V with D, D with T, and T with P. (I admit, T probably wouldn’t be confused with P, but I wanted to get a 5-cycle. So let’s go with it.) Our aim is to eliminate all possibility of confusion.

One way to do this would be to only communicate using P and V — or any other pair of non-adjacent vertices on the graph. This would certainly work, but it seems a shame: we have five letters at our disposal, and we’re not managing to do any better than if we had just two. In other words, we’re only communicating one bit of information per letter transmitted. That’s not very efficient.

There’s something smarter we can do. Let’s think not about single letters, but pairs of letters. How many non-confusable ordered pairs are there? Certainly, none of the pairs

(P, P),   (P, V),   (V, P),   (V, V)

could be mistaken for any of the others. That’s still no improvement on a two-letter alphabet, though. But more sneakily, we could use

(P, P),   (B, V),   (V, T),   (D, B),   (T, D).

These are mutually distinguishable. To explain why, it will probably make life easier if I switch from letters to numbers, so that the graph becomes

Five-cycle with vertices labelled 0 to 4

and the five pairs listed are

(0, 0),   (1, 2),   (2, 4),   (3, 1),   (4, 3).

For instance, if I transmit (1, 2) then you might hear (1, 1), or (0, 3), or in fact any of nine possibilities; but since the only one of them that’s on the list is (1, 2), you’d know you’d misheard. (In other words, you’d detect the error. You wouldn’t be able to correct it: for instance, (0, 3) could equally be a mishearing of (4, 3).)

What this means is that using two letters, we can transmit one of five possibilities. And that’s an improvement on binary. It’s as if we were using an alphabet with 5=2.23\sqrt{5} = 2.23\ldots reliably distinguishable letters.

Obviously, we could take this further and use blocks of nn letters rather than 22, hoping for further savings in efficiency. In this particular example, it turns out that there’s nothing more to be gained: the five-pair coding is the best there is. In the jargon, the ‘Shannon capacity’ of our graph is 5\sqrt{5}.

All I’ll do in the rest of the post is state the general definition of Shannon capacity. I’ll need to take a bit of a run-up.

For the purposes of this post, a graph is a finite, undirected, reflexive graph without multiple edges. ‘Reflexive’ means that every vertex has a loop on it (that is, an edge from it to itself). Typically, graph theorists deal with irreflexive graphs, in which no vertex has a loop on it.

In a slightly comical way, reflexive and irreflexive graphs are in canonical one-to-one correspondence. (Simply adjoin or delete loops everywhere.) But there are two reasons why I want to buck the convention and use reflexive graphs:

  1. As in the example, the vertices of the graph are supposed to be thought of as letters, and an edge between two letters means that one could be heard as the other. On that basis, every vertex should have a loop on it: if I say P, you might very well hear P!

  2. The homomorphisms are different. A graph homomorphism is a map of the underlying vertex-set that preserves the edge-relation: if xx is adjacent to yy then f(x)f(x) is adjacent to f(y)f(y). If GG and HH are two irreflexive graphs, and G RG_R and H RH_R the corresponding reflexive graphs, then Hom(G,H)Hom(G R,H R)Hom(G, H) \subseteq Hom(G_R, H_R), and in general it’s a proper subset. In other words, there is a proper inclusion of subcategories

(irreflexive graphs)(reflexive graphs) (irreflexive  graphs) \subset (reflexive  graphs)

which is bijective on objects. As we’ll see, products in the two categories are different, and that will matter.

Coming back to communication down a noisy phone line, a set of letters is ‘independent’ if none of them can be mistaken for any of the others. Formally, given a graph GG, an independent set in GG is a subset SS of the vertices of GG such that if s 1,s 2Ss_1, s_2 \in S are adjacent then s 1=s 2s_1 = s_2.

The independence number α(G)\alpha(G) of a graph GG is the largest cardinality of an independent set in GG. For example, when GG is the 5-cycle above, {P,V}\{P, V\} is an independent set and α(G)=2\alpha(G) = 2. It’s the “effective size of the alphabet” if you’re taking things one letter at a time.

To upgrade to the superior, multi-letter approach, we need to think about tuples of vertices — in other words, products of graphs.

In graph theory, there are various products of interest, and there’s a sort of hilarious convention for the symbol used. It goes as follows. Let II denote the graph o—o consisting of two vertices joined by an edge, and suppose we have some kind of product of graphs. Then the convention is that the symbol used to denote that product will be a picture of the product of II with itself. For example, this is the case for the products \Box, ×\times, and \boxtimes.

The last one, \boxtimes, is called the strong product, and it’s what we want here. It’s simply the product in the category of reflexive graphs. Explicitly, the vertex-set of GHG \boxtimes H is the product of the vertex-sets of GG and HH, and (g 1,h 1)(g_1, h_1) is adjacent to (g 2,h 2)(g_2, h_2) iff g 1g_1 is adjacent to g 2g_2 and h 1h_1 is adjacent to h 2h_2. You can check that III \boxtimes I is the graph that looks like \boxtimes.

(If we’d worked in the category of irreflexive graphs, we’d have got a different product: it’s the one denoted by ×\times.)

Let’s check that the strong product is really what we want for our application. Two vertices are supposed to be adjacent if one could be confused with the other. Put another way, two vertices are non-adjacent if they can be reliably distinguished from each other. We can distinguish (g 1,h 1)(g_1, h_1) from (g 2,h 2)(g_2, h_2) if either we can distinguish g 1g_1 from g 2g_2 or we can distinguish h 1h_1 from h 2h_2. So, (g 1,h 1)(g_1, h_1) and (g 2,h 2)(g_2, h_2) should be non-adjacent if either g 1g_1 and g 2g_2 are non-adjacent or h 1h_1 and h 2h_2 are non-adjacent. And that’s just what happens in the strong product.

For instance, let C 5C_5 be the 5-cycle shown above. Then the vertices

(0, 0),   (1, 2),   (2, 4),   (3, 1),   (4, 3).

of C 5C 5C_5 \boxtimes C_5 form an independent set of cardinality 5. It’s not hard to see that there’s no larger independent set in C 5C 5C_5 \boxtimes C_5, so

α(C 5C 5)=5 \alpha(C_5 \boxtimes C_5) = 5

—that is, C 5C 5C_5 \boxtimes C_5 has independence number 55.

For trivial reasons, if SS is an independent set in GG and TT is an independent set in HH then S×TS \times T is an independent set in GHG \boxtimes H. We saw this in the case G=H=C 5G = H = C_5 and S=T={P,V}S = T = \{P, V\}. Hence

α(GH)α(G)α(H). \alpha(G \boxtimes H) \geq \alpha(G) \cdot \alpha(H).

In particular,

α(G 2)α(G) 2 \alpha\bigl(G^{\boxtimes 2}\bigr) \geq \alpha(G)^2

or equivalently,

α(G 2) 1/2α(G). \alpha\bigl(G^{\boxtimes 2}\bigr)^{1/2} \geq \alpha(G).

In our example, this says that α(C 5 2) 1/22\alpha\bigl(C_5^{\boxtimes 2}\bigr)^{1/2} \geq 2. In fact, we know that α(C 5 2) 1/2=5=2.23\alpha\bigl(C_5^{\boxtimes 2}\bigr)^{1/2} = \sqrt{5} = 2.23\ldots, which represents an improvement: more economical communication.

The Shannon capacity measures how economically one can communicate without ambiguity, allowing the use of letter blocks of arbitrary size. Formally, the Shannon capacity of a graph GG is

Θ(G):=sup k1α(G k) 1/k. \Theta(G) := \sup_{k \geq 1} \alpha\bigl(G^{\boxtimes k}\bigr)^{1/k}.

For instance, we saw that Θ(C 5)=5\Theta(C_5) = \sqrt{5}. This means that if you want to communicate using vertices of C 5C_5, avoiding ambiguity, then you can do it as fast as if you were communicating with an alphabet containing 5\sqrt{5} completely distinguishable letters. You might call it the “effective number of vertices” in the graph… a phrase I’ll come back to next time.

Shannon also showed that

Θ(G)=lim kα(G k) 1/k. \Theta(G) = \lim_{k \to \infty} \alpha\bigl(G^{\boxtimes k}\bigr)^{1/k}.

I don’t know the proof. Also, I don’t know whether α(G k) 1/k\alpha\bigl(G^{\boxtimes k}\bigr)^{1/k} is actually increasing in kk, which would of course imply this. (Update: Tobias Fritz answers both questions in a comment below.)

Update A few minutes after posting this, I discovered a coincidence: the Shannon capacity of a graph was also the subject of a blog post by Kenneth Regan at Buffalo, just a month ago. He also discusses the Lovász number of a graph, a quantity related to the Shannon capacity which I’d planned to mention next time.

The Shannon capacity is very hard to compute. Regan mentions that even the Shannon capacity of the 7-cycle C 7C_7 is unknown!

 

 Next time: How this connects to the concepts of maximum diversity and magnitude.

 

Posted at August 10, 2013 3:10 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2645

35 Comments & 0 Trackbacks

Re: The Shannon Capacity of a Graph, 1

Here is some more information; I’ve recently been looking at the Shannon capacity of graphs in the context of quantum contextuality, so I can say a little bit more.

The sequence a k:=α(G k) 1/ka_k:=\alpha(G^{\boxtimes k})^{1/k} is not monotonically increasing or non-decreasing in general. I think that G=C 5G=C_5 itself is an example of this, where a 3=α(G 3) 1/3=10 1/3<5a_3=\alpha(G^{\boxtimes 3})^{1/3}=10^{1/3}\lt\sqrt{5}. Other surprising behaviors of such “independence sequences” have been found in a paper of Alon and Lubetzky.

That the independence sequence a ka_k nevertheless converges is due to α(G (j+k))α(G j)α(G k)\alpha(G^{\boxtimes(j+k)})\geq\alpha(G^{\boxtimes j})\alpha(G^{\boxtimes k}), which holds since the cartesian product of an independent set in G jG^{\boxtimes j} with an independent set in G kG^{\boxtimes k} is an independent set in G (j+k)G^{\boxtimes (j+k)}. This inequality implies convergence of the sequence logα(G k)k=loga k \frac{\log \alpha(G^{\boxtimes k})}{k}=\log a_k by virtue of Fekete’s lemma for superadditive sequences.

Looking forward to see how Shannon capacity relates to diversity and magnitude!

Posted by: Tobias Fritz on August 10, 2013 4:29 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Great — thanks for setting me straight. You may have caught some last-minute edits of that paragraph: I saw the claim in Kenneth Regan’s post that the sequence was increasing, did a quick calculation that I thought confirmed it, realized a few minutes later that my calculation was wrong, and then started to doubt whether the claim was true at all. Your comment settles it.

(To be clear: when I say “increasing”, I mean it in the weak sense. I know lots of people like to say “non-decreasing”, but that’s long struck me as a bit bonkers.)

As your post made me realize, it can’t possibly be the case that both (i) Θ(C 5)=5\Theta(C_5) = \sqrt{5}, and (ii) the sequence (a k)=(α(C 5 k) 1/k)(a_k) = \Bigl(\alpha(C_5^{\boxtimes k})^{1/k}\Bigr) is increasing. For since a 2=5a_2 = \sqrt{5}, (i) and (ii) would together imply that a 3=5a_3 = \sqrt{5}. But a 3a_3 is some positive integer to the power of 1/31/3, so 5 3\sqrt{5}^3 would have to be an integer, which it isn’t.

Posted by: Tom Leinster on August 10, 2013 4:51 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Oh, now I understand your email and that it actually was intended for me. Thanks! And I see that you’ve already commented on Kenneth Regan’s blog as well.

Noticing that 5 3\sqrt{5}^3 is not integer is a very neat argument for showing that the independence sequence is not increasing! I didn’t know that one could put it that way without actually computing any further independence numbers.

Posted by: Tobias Fritz on August 10, 2013 5:09 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

I know lots of people like to say “non-decreasing”, but that’s long struck me as a bit bonkers.

I don’t like to say “nondecreasing”, but if I always say “nondecreasing”/”strictly increasing” then I never have to go back and clarify what I meant by “increasing”. I similarly try always to say “nonnegative”/”strictly positive”. It can sound silly, but at least it’s unambiguous, regardless of the audience’s background.

Posted by: Mark Meckes on August 11, 2013 6:11 AM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

I found the awkward so settled on <-preserving or \le-preserving, as appropriate.

Posted by: Tom Ellis on August 11, 2013 10:33 AM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

I mean “found that awkward …”

Posted by: Tom Ellis on August 11, 2013 10:34 AM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

That solution works well in a written medium, but probably isn’t any less awkward when speaking out loud.

Posted by: Mark Meckes on August 11, 2013 12:09 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

I agree, Mark, that certainly has its advantages. Something I do myself which I think is a bit bonkers is to use “nonnegative” to mean “0\geq 0”. It’s pretty odd to describe a thing by saying what it’s not. (Though at least “nonnegative” really does mean “not negative”, while “non-decreasing” doesn’t mean “not decreasing”.) I think the French have it right in using positif to mean 0\geq 0 and strictement positif for >0\gt 0.

Posted by: Tom Leinster on August 11, 2013 12:14 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

It’s pretty odd to describe a thing by saying what it’s not.

Odd perhaps, but not so uncommon that it isn’t a mainstay of not a few examples of writing which can’t be parsed without difficulty.

“non-decreasing” doesn’t mean “not decreasing”.

You can almost make that work by interpreting it as “not decreasing on any subset”. But since “decreasing” alone means “decreasing on every subset” you end up applying “not” to only part of “decreasing”.

I think the French have it right in using positif to mean 0\ge 0 and strictement positif for > 00.

Probably. But anglophones are strangely inconsistent on this point, with usage correlating with subfield, and in any case part of the differences in audience background we have to deal with is different linguistic backgrounds. I’m reminded of my favorite quote about mathematicians, by Goethe:

Die Mathematiker sind eine Art Franzosen; redet man mit ihnen, so übersetzen sie es in ihre Sprache, und dann ist es alsobald ganz etwas anderes.

Roughly:

Mathematicians are a species of Frenchman; when one speaks with them, they translate it into their language, and from then on it is something completely different.

Posted by: Mark Meckes on August 11, 2013 1:39 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

There are English-speaking mathematicians who say “positive” to mean “nonnegative”??? Do they also say “greater” to mean “greater than or equal to”?

Posted by: Mike Shulman on August 11, 2013 5:39 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

There are English-speaking mathematicians who say “positive” to mean “nonnegative”???

In certain parts of analysis (French-influenced subfields?) that’s quite common, but it’s not a very self-consistent practice. I don’t think I’ve ever heard anyone call 00 a “positive integer” (though we could waste a lot of time and energy on the question of whether it’s a “natural number”), but 00 is sometimes a “positive number”, and a “positive function” is usually allowed to take on the value 00. With more complicated objects it becomes even more common to use “positive” in a weak sense. For example, “positive operator” typically means positive semidefinite, not positive definite.

It all gets to be quite a mess, of course. I think the root of it is that people favor the simplest term for the idea they work with most often. But since different people work more often with different things…

Do they also say “greater” to mean “greater than or equal to”?

Colloquially, yes. In writing, I’m not sure.

Posted by: Mark Meckes on August 11, 2013 6:13 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

In operator (algebra) theory, positive operators generalize *non-negative* numbers: a multiple of the identity operator is positive if and only if it is a non-negative multiple. One can understand this use of “positive” as shorthand for “positive semidefinite”.

This seems very sensible terminology and might be an example of what Mark refers to. I think there is also a notion of “strictly positive operator”, but I don’t know what exactly it means.

Posted by: Tobias Fritz on August 11, 2013 9:35 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Analysts, of course, have to distinguish between x:X,f(x)>0 \forall x : X, f(x) \gt 0 and x:βX,lim xf>0 \forall x : \beta X, \lim_x f \gt 0 which is more-or-less the same as ε>0x:X,f(x)>ε \exists \varepsilon \gt 0 \forall x : X, f(x) \gt \varepsilon

Posted by: Jesse McKeown on August 11, 2013 11:02 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Hmm, that seems to me like poorly chosen terminology. If there are two related-but-distinct concepts X and Y, and you have a more general concept which generalizes X, then you shouldn’t call it a Y. (I see historically how it might have happened, from “positive” to “positive definite” to “positive semidefinite” to “positive”, but that doesn’t make the end result sensible.)

Posted by: Mike Shulman on August 12, 2013 6:27 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

I’m speaking beyond my knowledge here, but I imagine it’s the case that positive operators (in the non-strict sense that Tobias mentioned) are much more interesting and important than strictly positive operators. And if they’re the central object of study, it’s intolerable to keep calling them by some name such as “nonnegative” or “non-strictly positive” or “positive semidefinite”. You want something short and snappy, like “positive”.

In Practical Foundations of Mathematics, Paul Taylor explains why (unusually for someone with a background in category theory) he uses \subset to mean what I’d call \subseteq. His argument is that being a possibly-improper subset is the more important and common condition than being a proper subset — and as the primary concept, it should get a simpler symbol. I have some sympathy with this.

I’m pretty sure he doesn’t go as far as saying that because “less than or equal to” is a more important and common condition than “strictly less than”, he’s going to use <\lt for what everyone else calls \leq. That would be… taxing. But again, I’d have some sympathy for such a position.

Posted by: Tom Leinster on August 12, 2013 8:17 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

I agree that important concepts need short and snappy names, but I don’t think that that justifies appropriating a word or symbol that already has a different meaning. But I guess I’m familiar with the fact that some people feel differently.

Posted by: Mike Shulman on August 13, 2013 1:18 AM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

If you want to see some really unfortunate terminology along these lines, consider the following: a function f:Gf:G \to \mathbb{C} on an abelian group GG is called “positive definite” if, for each finite subset AGA \subseteq G, the matrix [f(ab)] a,bA[f(a-b)]_{a,b \in A} is positive semidefinite; if for each AA the matrix is positive definite, then ff is called strictly positive definite. “Positive semidefinite function” is not in common use.

Then there’s “nonnegative definite” (matrix, operator, bilinear form, etc.), which is sometimes used as a synonym for “positive semidefinite”, even though such a thing is not in general “definite”.

Posted by: Mark Meckes on August 12, 2013 11:20 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

What exactly is “definite” about something “positive definite”? I’ve never understood that terminology (and “nonnegative definite” seems to me like a much more obvious generalization of it than “positive semidefinite”).

Posted by: Mike Shulman on August 13, 2013 6:40 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

If you use the definitions at [[inner product space#definite]], then ‘positive’, ‘semidefinite’, and ‘definite’ all have independent meanings, and ‘positive definite’ literally means both positive and definite. (Also, ‘positive semidefinite’ is redundant, but I advocate its use to avoid confusion.)

Posted by: Toby Bartels on September 15, 2013 6:43 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Well, what I’ve heard said before is that the “definite” part of “positive definite” is supposed to refer to the nondegeneracy condition. But looking around a bit now, I find that it’s more standard to say that it refers to the fact that (say, for a bilinear form) x,x\langle x, x \rangle takes on only positive values for nonzero xx. So “nonnegative definite” certainly is a more logical generalization, and I retract the second paragraph of my last comment.

Posted by: Mark Meckes on August 13, 2013 8:08 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Come to think of it, that’s also my favorite quote about Frenchman.

And by the way: sorry, Tom, for hijacking this comment thread. I am interested in the post itself, and I’m looking forward to the sequel.

Posted by: Mark Meckes on August 11, 2013 2:25 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

No apology necessary — after all, I was the one who used the provocative phrase “a bit bonkers”, and who doesn’t like to air their opinions on terminlogy?

(I like the Goethe quote too.)

Posted by: Tom Leinster on August 11, 2013 10:55 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

I know lots of people like to say “non-decreasing”, but that’s long struck me as a bit bonkers.

You can also do ‘nowhere decreasing’ or ‘never decreasing’ (depending on whether you prefer a spatial or temporal metaphor for your variables, and with a hyphen if desired). This even works for partial orders if you add ‘nohow’ and interpret xyx \leq y as that xx has a smaller (or equal) value than yy has in each of various (possibly interacting) ways. (I don't really advocate this, but it can be done.)

Posted by: Toby Bartels on September 15, 2013 7:08 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Jamie Vicary explained Shannon capacity to me last summer, using the same example of the 5-cycle C 5C_5 and its ‘strong square’ C 5 2C_5^{\boxtimes 2}. But he presented it in the form of a puzzle: find as many pairwise nonadjacent vertices as you can in C 5 2C_5^{\boxtimes 2}.

The puzzle was fun and not too hard because he drew C 5 2C_5^{\boxtimes 2}—which you, alas, but quite forgivably, did not. You can draw it as a little grid of squares with the convention that opposite edges are identified. But then you can replace the vertices of this grid by the squares in this grid, and the puzzle becomes:

How many kings can you put on a 5×55 \times 5 wraparound chessboard so that no king can capture another?

And then the answer involves knight moves, and the relation to

5=2 2+1 2\sqrt{5} = \sqrt{2^2 + 1^2}

becomes quite beautifully visible!

I eagerly await future posts, since we never got too terribly far doing anything with the idea of Shannon capacity.

Posted by: John Baez on August 11, 2013 3:36 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

he drew C 5 2C_5^{\boxtimes 2}—which you, alas, but quite forgivably, did not.

Heh. Yes, I spent a good half-minute contemplating the horror of drawing a kind of uncomfortable-to-sit-on torus representing C 5C 5C_5 \boxtimes C_5. The grid solution is much better!

But I don’t fully understand your comment. I can see that the five kings are all a knight’s move apart, and that the Euclidean length of a knight’s move is 5=2 2+1 2\sqrt{5} = \sqrt{2^2 + 1^2}. However, I don’t see why that’s the same as the “other” 5\sqrt{5} — that is, the square root of the independence number of C 5 2C_5^{\boxtimes 2}. Can you give me a clue?

Posted by: Tom Leinster on August 11, 2013 11:02 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Okay, here’s a clue:

5 25 2=5 \frac{5^2}{\sqrt{5}^2} = 5

I’ll be glad to explain it if it’s too cryptic.

Posted by: John Baez on August 12, 2013 3:49 AM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

tiling of 5 by 5 grid into 5 square tiles

Posted by: Tom Leinster on August 12, 2013 11:47 AM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Is that what you meant?

(Don’t know why one vertical and one horizontal line have come out heavier than the others; that’s just an accident.)

Posted by: Tom Leinster on August 13, 2013 12:14 AM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Yes, that’s exactly the picture I was hinting at!

You’re taking a square with sides of length 5 and neatly chopping into 5 squares with length 5\sqrt{5}, using knight moves… so you get to code for 5 different expressions using two letters without ambiguity, getting a Shannon capacity of 5\sqrt{5}.

The two 5\sqrt{5}’s here have opposite, or reciprocal, meanings: one says how far apart the code words need to be, while the other says how much capacity your code has… but they’re related.

Posted by: John Baez on August 13, 2013 10:38 AM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

In the first comment, Tobias linked to a paper of his:

Tobias Fritz, Anthony Leverrier, Ana Belén Sainz, A combinatorial approach to nonlocality and contextuality, arXiv:1212.4084.

I’ve just been skimming through it, and I’d like to highlight their Conjecture A.2.1. It’s actually several related conjectures.

They say that a graph GG is single-shot if α(G)=Θ(G)\alpha(G) = \Theta(G). Remember that α(G)\alpha(G) is the independence number of GG (the largest cardinality of a set of unrelated vertices), and that the Shannon capacity Θ(G)\Theta(G) is given by

Θ(G)=sup kα(G k) 1/k=lim kα(G k) 1/k. \Theta(G) = \sup_k \alpha(G^{\boxtimes k})^{1/k} = \lim_{k \to \infty} \alpha(G^{\boxtimes k})^{1/k}.

In particular, α(G)Θ(G)\alpha(G) \leq \Theta(G). “Single-shot” means that taking higher powers of your graph gives you no efficiency savings at all: for instance, the 5-cycle C 5C_5 is not single-shot, because we were able to make a clever saving by considering pairs of vertices.

Their conjecture says that if G 1G_1 and G 2G_2 are single-shot, then:

  1. α(G 1G 2)=α(G 1)α(G 2)\alpha(G_1 \boxtimes G_2) = \alpha(G_1) \alpha(G_2);
  2. Θ(G 1G 2)=Θ(G 1)Θ(G 2)\Theta(G_1 \boxtimes G_2) = \Theta(G_1) \Theta(G_2);
  3. Θ(G 1+G 2)=Θ(G 1)+Θ(G 2)\Theta(G_1 + G_2) = \Theta(G_1) + \Theta(G_2),

where in (3), ++ means disjoint union.

These seem very simple statements not to be known!

Posted by: Tom Leinster on August 12, 2013 2:00 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

By now, all of these conjectures have been disproven! There are counterexamples to Conjecture 7.5.1(c) found by our collaborator Antonio Acín. By virtue of the implications displayed in Figure 12, these translate into counterexamples to the conjectures mentioned by Tom. We are currently preparing a follow-up paper containing these results.

The counterexamples rely crucially on graphs whose Lovász number is strictly greater than their Shannon capacity; such graphs have been found in Haemers’ paper “An upper bound for the Shannon capacity of a graph”.

Haemers’ bound is well worth knowing due to its sheer simplicity: let BB be a matrix over some field with rows and columns indexed by the vertices of the graph GG, such that B vw=0B_{vw}=0 if two distinct vertices vv and ww are adjacent, while B vv0B_{vv}\neq 0 on the diagonal. Then every independent set of vertices induces a submatrix which is diagonal of full rank, and hence rank(B)α(G)\mathrm{rank}(B)\geq\alpha(G). Since B nB^{\otimes n} satisfies the analogous properties for G nG^{\boxtimes n}, we have α(G n)rank(B n)=rank(B) n\alpha(G^{\boxtimes n})\leq \mathrm{rank}(B^{\otimes n})=\mathrm{rank}(B)^n. This implies Θ(G)rank(B)\Theta(G)\leq \mathrm{rank}(B).

(The conditions on BB are curiously contrary to Tom’s philosophy of working with reflexive graphs…)

Posted by: Tobias Fritz on August 13, 2013 2:01 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Oh well! Good that you’ve uncovered the truth.

Something seems to be wrong in the conditions on BB that you list, otherwise it won’t be true that

every independent set of vertices induces a submatrix which is diagonal.

The paper of Haemers that you link to agrees with what you wrote, but the Wikipedia article on Shannon capacity changes

B vw=0B_{v w} = 0 if two distinct vertices vv and ww are adjacent

to

B vw=0B_{v w} = 0 if two distinct vertices vv and ww are not adjacent

(my paraphrasing), and cites that same paper of Haemers with the note that they’re correcting a typo in it. I think that’s got to be right.

So if we view GG as reflexive, the conditions on BB are that for vertices vv and ww,

v=wB vw0{v,w}E(G) v = w \quad \implies \quad B_{v w} \neq 0 \quad \implies \quad \{v,w\} \in E(G)

where E(G)E(G) is the set of edges. That seems to suggest that it’s more convenient here to view GG as reflexive than irreflexive (not that I have a global preference for one over the other).

Posted by: Tom Leinster on August 13, 2013 3:53 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

By the way, it should probably be mentioned that counterexamples to the analogous conjectures for general graphs (as opposed to single-shot) have been known for quite some time.

If I recally correctly, both Θ(G 1G 2)=Θ(G 1)Θ(G 2)\Theta(G_1\boxtimes G_2)=\Theta(G_1)\Theta(G_2) and Θ(G 1+G 2)=Θ(G 1)+Θ(G 2)\Theta(G_1+G_2)=\Theta(G_1)+\Theta(G_2) were disproved in Haemers 1979 paper “On some problems of Lovász concerning the Shannon capacity of a graph”. (I currently can’t find any full-text version.)

Posted by: Tobias Fritz on August 13, 2013 2:12 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

You wrote “we saw that Θ(C 5)=2\Theta(C_5) = 2”, which must be a typo since above you explain that Θ(C 5)5>2\Theta(C_5) \ge \sqrt{5} \gt 2. In fact, it is true that Θ(C 5)=5\Theta(C_5) = \sqrt{5} but it takes quite a bit of cleverness to show. Shannon managed to compute the capacity of all graphs with 5 vertices or fewer except for C 5C_5, for which he showed that 5Θ(C 5)52\sqrt{5} \le \Theta(C_5) \le \frac{5}{2}. More than 20 years after Shannon’s work, Laszlo Lovász proved that Θ(C 5)=5\Theta(C_5) = \sqrt{5} by what seems to me to be a very clever strategy.

Lovász’s paper is On the Shannon capacity of a graph, IEEE Trans. Information Theory 25 (1979), 1-7. I read his proof in the charming Proofs from the book by Martin Aigner and Günter M. Ziegler.

Posted by: Omar Antolín-Camarena on August 16, 2013 7:14 PM | Permalink | Reply to this

Re: The Shannon Capacity of a Graph, 1

Oops, thanks. Typo fixed now.

I’m actually in the middle of writing Part 2, which mentions Lovász’s proof that Θ(C 5)=5\Theta(C_5) = \sqrt{5}. I’d guessed, but didn’t know for sure, that Lovász was the first person to prove this. Thanks for confirming it and for explaining the history.

Posted by: Tom Leinster on August 17, 2013 6:31 PM | Permalink | Reply to this

Post a New Comment