The Shannon capacity of a union

Noga Alon

doi:10.1007/PL00009824

The Shannon capacity of a union

Noga Alon

Research output: Contribution to journal › Article › peer-review

115 Scopus citations

Abstract

For an undirected graph G = (V, E), let Gⁿ denote the graph whose vertex set is Vⁿ in which two distinct vertices (u₁, u₂, . . . , u_n) and (v₁, v₂, . . . , v_n) are adjacent iff for all i between 1 and n either u_i = v_i or u_iv_i ∈ E. The Shannon capacity c(G) of G is the limit lim_n→∞ (α(Gⁿ))^1/n, where α(Gⁿ) is the maximum size of an independent set of vertices in Gⁿ. 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 language	English (US)
Pages (from-to)	301-310
Number of pages	10
Journal	Combinatorica
Volume	18
Issue number	3
DOIs	https://doi.org/10.1007/PL00009824
State	Published - 1998
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/PL00009824

Cite this

@article{c01b7ed9421548cfb147f8bfd69db611,

title = "The Shannon capacity of a union",

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.",

author = "Noga Alon",

note = "Funding Information: Mathematics Subject Classi cation (1991): 05C35, 05D10, 94C15 Part of this work was done at DIMACS and at the Institute for Advanced Study, Princeton, NJ 08540, USA. Research supported in part by a grant from the the Israel Science Foundation, by a State of New Jersey grant and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.",

year = "1998",

doi = "10.1007/PL00009824",

language = "English (US)",

volume = "18",

pages = "301--310",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "3",

}

TY - JOUR

T1 - The Shannon capacity of a union

AU - Alon, Noga

N1 - Funding Information: Mathematics Subject Classi cation (1991): 05C35, 05D10, 94C15 Part of this work was done at DIMACS and at the Institute for Advanced Study, Princeton, NJ 08540, USA. Research supported in part by a grant from the the Israel Science Foundation, by a State of New Jersey grant and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0032411859

UR - https://www.scopus.com/pages/publications/0032411859#tab=citedBy

U2 - 10.1007/PL00009824

DO - 10.1007/PL00009824

M3 - Article

AN - SCOPUS:0032411859

SN - 0209-9683

VL - 18

SP - 301

EP - 310

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -

The Shannon capacity of a union

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this