The Shannon capacity of a union

Research output: Contribution to journalArticlepeer-review

110 Scopus citations

Abstract

For an undirected graph G = (V, E), let Gn denote the graph whose vertex set is Vn in which two distinct vertices (u1, u2, . . . , un) and (v1, v2, . . . , vn) are adjacent iff for all i between 1 and n either ui = vi or uivi ∈ E. The Shannon capacity c(G) of G is the limit limn→∞ (α(Gn))1/n, where α(Gn) is the maximum size of an independent set of vertices in Gn. We show that there are graphs G and H such that the Shannon capacity of their disjoint union is (much) bigger than the sum of their capacities. This disproves a conjecture of Shannon raised in 1956.

Original languageEnglish (US)
Pages (from-to)301-310
Number of pages10
JournalCombinatorica
Volume18
Issue number3
DOIs
StatePublished - 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'The Shannon capacity of a union'. Together they form a unique fingerprint.

Cite this