New lower bound on the Shannon capacity of C7 from circular graphs

Abstract

We give an independent set of size $367$ in the fifth strong product power of $C_7$, where $C_7$ is the cycle on $7$ vertices. This leads to an improved lower bound on the Shannon capacity of $C_7$: $\Theta (C_7)\ge 367^{1/5}>3.2578$. The independent set is found by computer, using the fact that the set $\{t\cdot (1,7,7^2,7^3,7^4)|t\in {\mathbb{Z}}_{382}\}\subseteq {\mathbb{Z}}_{382}^5$ is independent in the fifth strong product power of the circular graph $C_{108,382}$. Here the circular graph $C_{k,n}$ is the graph with vertex set ${\mathbb{Z}}_n$, the cyclic group of order $n$, in which two distinct vertices are adjacent if and only if their distance (mod $n$) is strictly less than $k$.

arXiv comment5 pages. Some changes have been made based on comments of the referees. Accepted for publication in Information Processing Letters

Cited by in corpus (6)

• Observations on Graph Invariants with the Lovász $\vartheta$-Function
• Quantum asymptotic spectra of graphs and non-commutative graphs, and quantum Shannon capacities
• Unified bounds for the independence number of graphs
• The Haemers bound of noncommutative graphs
• Variable-Length Coding for Zero-Error Channel Capacity
• On Upper Bounding Shannon Capacity of Graph Through Generalized Conic Programming