The Shannon capacity of a union (Q1297763): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 11:53, 31 January 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