A Bound on the Shannon Capacity via a Linear Programming Variation

Research paper by Sihuang Hu, Itzhak Tamo, Ofer Shayevitz

Indexed on: 08 Sep '18Published on: 04 Sep '18Published in: SIAM Journal on Discrete Mathematics


SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2229-2241, January 2018. 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ász 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.