New lower bounds for the Shannon capacity of odd cycles

K. Ashik Mathew, Patric R J Östergård*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

8 Citations (Scopus)


The Shannon capacity of a graph G is defined as (Formula presented.) where (Formula presented.) is the independence number of G. The Shannon capacity of the cycle (Formula presented.) on 5 vertices was determined by Lovász in 1979, but the Shannon capacity of a cycle (Formula presented.) for general odd p remains one of the most notorious open problems in information theory. By prescribing stabilizers for the independent sets in (Formula presented.) and using stochastic search methods, we show that (Formula presented.), (Formula presented.), (Formula presented.), and (Formula presented.). This leads to improved lower bounds on the Shannon capacity of (Formula presented.) and (Formula presented.): (Formula presented.) and (Formula presented.).

Original languageEnglish
Pages (from-to)13-22
Number of pages10
Issue number1-2
Early online date25 Mar 2016
Publication statusPublished - Jul 2017
MoE publication typeA1 Journal article-refereed


  • Cube packing
  • Independent set
  • Shannon capacity
  • Zero-error capacity


Dive into the research topics of 'New lower bounds for the Shannon capacity of odd cycles'. Together they form a unique fingerprint.

Cite this