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.

, ,
doi.org/10.1016/j.indag.2022.08.009
Indagationes Mathematicae
Networks and Optimization

Schrijver, A. (2022). On the Shannon capacity of sums and products of graphs. Indagationes Mathematicae. doi:10.1016/j.indag.2022.08.009