Recent findings on the Shannon capacity of graphs

The Shannon capacity of a graph, as introduced in Shannon’s seminal paper (1956) on zero-error communication, plays a key role in understanding the synergy and interaction between zero-error information theory and graph theory. The importance of the Shannon capacity of graphs, together with the general intractability of its computation, has been emphasized in numerous works.

After introducing the notion of the Shannon capacity of graphs, this talk discusses several of our recent findings concerning the Shannon capacity of graphs. 

1) The Lovász function of a graph is a computable upper bound on the Shannon capacity of a graph, which is tight for certain graphs. A closed-form expression for this bound is derived for the family of strongly regular graphs, and examples are presented where the bound is attained. 

2) An open question concerning a variant of the Lovász function of a graph was introduced by Schrijver and independently by McEliece et al. (1978). The question of whether this variant provides an upper bound on the Shannon capacity of a graph was explicitly stated by Bi and Tang (2019). We present an explicit example of a graph on 32 vertices, which shows that, in contrast to the Lovász function, this variant does not necessarily upper bound the Shannon capacity of a graph. The example resolves this question, and it clarifies a subtle but significant distinction between these two closely related graph invariants. 

3) We provide a countably infinite family of connected graphs whose Shannon capacities are not attained by the independence number of any finite strong power; these are the first connected graphs having this property, as the previous constructions of such graphs were disconnected. 4) We provide an inequality that relates the Shannon capacities of the disjoint union of graphs and their strong product, and show some of its consequences.