Source-linked AI summary
New lower bound on the Shannon capacity of C7 from circular graphs
Sven Polak, Alexander Schrijver
TL;DR
The paper addresses the unknown Shannon capacity of C7 by seeking larger independent sets in powers of the cycle. It uses a computer-assisted adaptation of a structured independent set in a circular graph, obtaining an independent set of size 367 in C7^5 and hence Θ(C7) ≥ 367^1/5 > 3.2578.
Abstract
from arXiv · showhide
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$.
1 Introduction
The Shannon capacity of C7 remains unknown, and this paper improves its lower bound by constructing an independent set of size 367 in C7^5. The construction adapts an independent set from a circular graph, yielding Θ(C7) ≥ 367^1/5 > 3.2578.
1 Introduction
- For a graph G, G^d is the d-th strong product power, and α(G^d) is the largest set of pairwise nonadjacent vertices.The Shannon capacity is the asymptotic growth rate of these independence numbers: Θ(G) = lim d→∞ α(G^d)^(1/d).Source: §1 · p. 1
- 367 vertices in an independent set of C7^5 improve the Shannon-capacity lower bound to Θ(C7) ≥ 367^1/5 > 3.2578.The previous lower bound was 350^1/5 > 3.2271.Source: §1 · p. 2
- The Shannon capacity of C7 is still unknown, with an upper bound Θ(C7) ≤ ϑ(C7) < 3.3177.Determining Θ(C7) is described as a notorious open problem in extremal combinatorics.Source: §1 · p. 2
- The paper’s construction starts from a circular-graph independent set of size 382 and adapts it by removing vertices and adding new ones to obtain 367 vertices in C7^5.The original set does not translate directly because 382/108 > 7/2.Source: §1 · p. 2
2 Circular Graphs
The paper defines circular graphs and develops a computer-found independent set of size 382 in C^5_108,382, then explains how this construction relates to C^5_7.
Definitions
- Circular graph C_k,n has vertex set Z_n, with adjacency determined by cyclic distance being strictly less than k.The special case C_2,n is the ordinary cycle C_n.Source: §2 · p. 2
- Independence in a strong product power is equivalent to every pair of distinct words having coordinatewise distance at least k.The distance of two words is the maximum of their coordinate distances modulo n.Source: §2 · p. 2
Circular graph properties
- For circular graphs, homomorphisms preserve upper bounds on independence and Shannon capacity, and these quantities depend on the fraction n/k.The paper uses the homomorphism relation between circular graphs to connect different parameter choices.Source: §2 · pp. 2–3
Relation to C_7
- The construction does not directly yield an independent set in C^5_7 because 382/108 > 7/2.Section 3 therefore adapts the circular-graph independent set by removing and adding words.Source: §2 · p. 3
Circular graph construction
- The set S = {t · (1, 7, 7^2, 7^3, 7^4) | t ∈ Z_382} is independent in C^5_108,382.The verification reduces to checking nonzero elements of S and uses interval arguments together with Table 2.Source: §2 · p. 3, Table 2 · p. 3
3 Description of the method
The method transforms the 382-word construction into a set in C^5_7, removes conflicts, and searches for a maximum independent extension, obtaining 367 words.
Construction
- The procedure shifts every word, divides each coordinate by 54.5 using a floor operation, and interprets the resulting symbols in Z_7.It starts from S in C^5_108,382 and adds (40, 123, 40, 123, 40) modulo 382 before the coordinate conversion.Source: §3 · p. 3
Conflict removal
- After conversion, words are removed whenever another word is adjacent in C^5_7, leaving an independent set M of size 327.The removal condition is that all coordinate differences lie in {0, 1, 6} modulo 7.Source: §3 · p. 4
Extension
- 367 words form an independent set in C^5_7 after extending the conflict-free set M by 40 words.The auxiliary graph has 71 vertices and 85 edges; its maximum independent set has size 40, giving |R| = 327 + 40 = 367.Source: §3 · p. 4
Computational search
- The final set of size 367 was found computationally, but searches reported no independent set of size 368 or larger and no easy one-step extension.A local search also found no replacement of three words by four words that would produce size 368.Source: §3 · p. 4
Related construction
- A related construction with n = 4009, d = 5, and q = 27 gives α(C^5_11) ≥ 4009, but it does not improve the Shannon-capacity lower bound for C_11.The paper notes that Θ(C_11) ≥ 148^(1/3) > 5.2895 is larger than 4009^(1/5).Source: §3 · p. 4
Appendix: explicit code
The appendix gives an explicit 367-word independent set and states the resulting lower bound on the Shannon capacity of C7. It also lists the set using vertex strings.
- 367 words form an independent set in C7^5, yielding Θ(C7) ≥ 367^1/5 > 3.2578.Source: Appendix: explicit code · p. 4
- The appendix identifies this independent set as the set R from Section 3.Source: Appendix: explicit code · p. 4