On the Shannon capacity of sums and products of graphs

preprint2022arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.