On the Shannon capacity of sums and products of graphs

DOI10.1016/J.INDAG.2022.08.009zbMATH Open1504.05246arXiv2204.06853OpenAlexW4296196763MaRDI QIDQ2111251FDOQ2111251

Authors: Alexander Schrijver 

Publication date: 28 December 2022

Published in: Indagationes Mathematicae. New Series (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/2204.06853

Recommendations

• The Shannon capacity of a union
• On the normalized Shannon capacity of a union
• Shannon capacity and the categorical product
• On graphs in which the Shannon capacity is unachievable by finite product
• On product of association schemes and Shannon capacity

zbMATH Keywords

Shannon capacitystable set number

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Extremal problems in graph theory (05C35) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• On the Shannon capacity of a graph
• The Shannon capacity of a union
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph

Cited In (10)

• The asymptotic spectrum of graphs and the Shannon capacity
• Title not available (Why is that?)
• On graphs in which the Shannon capacity is unachievable by finite product
• An Analogue of the Shannon Capacity of a Graph
• On the variance of Shannon products of graphs
• Title not available (Why is that?)
• Shannon capacity and the categorical product
• On the normalized Shannon capacity of a union
• New lower bound on the Shannon capacity of \(C_7\) from circular graphs
• Sum-Networks From Incidence Structures: Construction and Capacity Analysis

This page was built for publication: On the Shannon capacity of sums and products of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111251)