Let Θ(G) denote the Shannon capacity of a graph G. We give an elementary proof of the equivalence, for any graphs G and H, of the inequalities Θ(G⊔H)>Θ(G)+Θ(H) and Θ(G⊠H)>Θ(G)Θ(H). This was shown independently by Wigderson and Zuiddam (2022) using Kadison–Dubois duality and the Axiom of choice.

, ,
Indagationes Mathematicae
CWI management

Schrijver, L. (2022). On the Shannon capacity of sums and products of graphs. Indagationes Mathematicae, 34(1), 37–41. doi:10.1016/j.indag.2022.08.009