On the Shannon capacity of sums and products of graphs

2022/04/14 by Schrijver, Alexander · 2 citations
#05C69 #94AXX #94BXX #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2204.06853

Abstract

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

Cited by

• Universality of asymptotic graph homomorphism
• Advances in the Shannon Capacity of Graphs

Related

• Advances in the Shannon Capacity of Graphs
• Shannon capacity and the categorical product
• Linear Shannon Capacity of Cayley Graphs
• The Shannon capacity of graph powers
• On Upper Bounding Shannon Capacity of Graph Through Generalized Conic Programming