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

Autor: Alexander Schrijver, Sven Polak
Přispěvatelé: Algebra, Geometry & Mathematical Physics (KDV, FNWI), Quantum Matter and Quantum Information
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Zdroj: Information Processing Letters, 143, 37-40
Information Processing Letters, 143, 37-40. Elsevier
ISSN: 1872-6119
0020-0190
DOI: 10.1016/j.ipl.2018.11.006
Popis: 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$.
Comment: 5 pages. Some changes have been made based on comments of the referees. Accepted for publication in Information Processing Letters
Databáze: OpenAIRE
Externí odkaz: