1
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

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

Preprint

,

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

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)\geq 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$$.

Most cited references6

• Record: found

The zero error capacity of a noisy channel

(1956)
Bookmark
• Record: found

On the Shannon capacity of a graph

(1979)
Bookmark
• Record: found

On Some Problems of Lovász Concerning the Shannon Capacity of a Graph

(1979)
Bookmark

Author and article information

Journal
22 August 2018
Article
1808.07438