TY - JOUR
T1 - New lower bound on the Shannon capacity of C7 from circular graphs.
AU - Polak, Sven C.
AU - Schrijver, Alexander
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2018
Y1 - 2018
N2 - We give an independent set of size 367 in the fifth strong product power of C7, where C7 is the cycle on 7 vertices. This leads to an improved lower bound on the Shannon capacity of C7: (C7) ≥ 3671/5 > 3.2578. The independent set is found by computer, using the fact that the set {t ·(1, 7, 72, 73, 74) | t ∈ Z382} ⊆ Z5 382 is independent in the fifth strong product power of the circular graph C108,382. Here the circular graph Ck,n is the graph with vertex set Zn, 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.
AB - We give an independent set of size 367 in the fifth strong product power of C7, where C7 is the cycle on 7 vertices. This leads to an improved lower bound on the Shannon capacity of C7: (C7) ≥ 3671/5 > 3.2578. The independent set is found by computer, using the fact that the set {t ·(1, 7, 72, 73, 74) | t ∈ Z382} ⊆ Z5 382 is independent in the fifth strong product power of the circular graph C108,382. Here the circular graph Ck,n is the graph with vertex set Zn, 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.
KW - shannon capacity
KW - independent set
KW - circular graph
KW - combinatorial problems
U2 - 10.1016/j.ipl.2018.11.006
DO - 10.1016/j.ipl.2018.11.006
M3 - Article
SN - 0020-0190
VL - abs/1808.07438
JO - Information Processing Letters
JF - Information Processing Letters
ER -