The Shannon capacity of a union (Q1297763): Difference between revisions

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.