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: |
FOS: Computer and information sciences
Computer Science - Information Theory Independent set Cyclic group 0102 computer and information sciences 02 engineering and technology 01 natural sciences Upper and lower bounds Combinatorial problems Theoretical Computer Science Combinatorics Channel capacity FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Mathematics - Combinatorics Circular graph Mathematics Information Theory (cs.IT) Graph Computer Science Applications Vertex (geometry) Shannon capacity 05C69 94A24 010201 computation theory & mathematics Signal Processing 020201 artificial intelligence & image processing Combinatorics (math.CO) Information Systems |
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: |
načítá se...