A bound on the Shannon capacity via a linear programming variation

DOI10.1137/17M115565XMaRDI QIDQ4584958zbMATH OpenOpenAlexWikidataFDO

Authors Sihuang Hu, Itzhak Tamo, Ofer Shayevitz

Publication date 5 September 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

index codinglinear programmingShannon capacity

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Fractional graph theory, fuzzy graph theory (05C72) Measures of information, entropy (94A17)

Abstract: We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lov'asz theta number and the Haemers minimum rank bound. As a by-product, we also obtain a new upper bound on the broadcast rate of Index Coding.

Recommendations

• On upper bounding Shannon capacity of graph through generalized conic programming
• Linear index coding via semidefinite programming
• Linear index coding via semidefinite programming
• On the Shannon capacity of a graph
• A comparison of the Delsarte and Lovász bounds

Cites work

• Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate
• scientific article; zbMATH DE number 5454110 (Why is no real title available?)
• scientific article; zbMATH DE number 3745081 (Why is no real title available?)
• Index Coding With Side Information
• Local chromatic number and Sperner capacity
• Nonlinear Index Coding Outperforming the Linear Optimum
• On a Problem of C. E. Shannon in Graph Theory
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• On the Shannon capacity of a graph
• The sandwich theorem

Cited in

(11)

• Improved lower bound on the Shannon capacity of C₇
• Probabilistic refinement of the asymptotic spectrum of graphs
• Topological bounds on the dimension of orthogonal representations of graphs
• On upper bounding Shannon capacity of graph through generalized conic programming
• Shannon capacity and the categorical product
• On the asymptotic tightness of the Shannon lower bound
• Linear index coding via semidefinite programming
• Linear index coding via semidefinite programming
• The zero-error capacity of binary channels with 2-memories
• Approximation of the Shannon capacity via matrix cone programming
• On the ratio of Shannon numbers of graphs

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: A bound on the Shannon capacity via a linear programming variation

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