Abstract:
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.
This talk addresses the following of our recent findings related to the Shannon capacity of graphs. 1) 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. 2) 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. 3) 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.
The results presented in this talk are based on two separate studies, the latter conducted in collaboration with Nitay Lavi as part of his Master thesis.
