The Shannon capacity of a union (Q1297763): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/pl00009824 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2030052209 / rank | |||
Normal rank |
Latest revision as of 11:39, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Shannon capacity of a union |
scientific article |
Statements
The Shannon capacity of a union (English)
0 references
14 September 1999
0 references
For an undirected graph \(G=(V,E)\), let \(G^n\) denote the graph whose vertex set is \(V^n\) in which two distinct vertices \((u_1,\dots,u_n)\) and \((v_1,\dots,v_n)\) are adjacent iff for all \(1\leq i\leq n\) either \(u_i=v_i\) or \(u_iv_i\in E\). The Shannon capacity \(c(G)\) of \(G\) is \(\lim_{n\to \infty}(\alpha(G^n))^{1/n}\), where \(\alpha(G^n)\) is the maximum size of an independent set of vertices in \(G^n\). In this paper it is shown 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.
0 references
Shannon capacity
0 references