On the Shannon capacity of sums and products of graphs

Abstract

Let $\Theta (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 $\Theta (G\bigsqcup H)>\Theta (G)+\Theta (H)$ and $\Theta (G⊠H)>\Theta (G)\Theta (H)$. This was shown independently by Wigderson and Zuiddam [2022] using Kadison-Dubois duality and the Axiom of choice.