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

08/22/2018

∙

by   Sven Polak, et al.

∙

0

∙

share

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: Θ(C_7)≥ 367^1/5 > 3.2578. The independent set is found by computer, using the fact that the set {t · (1,7,7^2,7^3,7^4) | t ∈Z_382}⊆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 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.