On the Shannon capacity of sums and products of graphs

DOI10.1016/J.INDAG.2022.08.009MaRDI QIDQ2111251zbMATH OpenOpenAlexFDO

Authors Alexander Schrijver

Publication date 28 December 2022

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

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

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)

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.

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

Cites work

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

Cited in

(10)

• The asymptotic spectrum of graphs and the Shannon capacity
• scientific article; zbMATH DE number 21092 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 4118412 (Why is no real title available?)
• 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)