On the normalized Shannon capacity of a union

Journal article

Let G 1 × G 2 denote the strong product of graphs G 1 and G 2, that is, the graph on V(G 1) × V(G 2) in which (u 1, u 2) and (v 1, v 2) are adjacent if for each i = 1, 2 we have ui = vi or u i v i E(G i). The Shannon capacity of G is c(G) = limn → α(Gn )1/n, where Gn denotes the n-fold strong power of G, and α(H) denotes the independence number of a graph H. The normalized Shannon capacity of G is Alon [1] asked whether for every < 0 there are graphs G and G satisfying C(G), C(G) < but with C(G + G) > 1 - . We show that the answer is no.

Authors: Keevash, P; Long, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Combinatorics, Probability and Computing
• Volume: 25
• Issue: 5
• Pages: 766-767
• Publication date: 2016-03-03
• DOI: 10.1017/S0963548316000055
• ISSN: 1469-2163 and 0963-5483
• Keywords: math.CO; SBTMR; 05C35, 94A05