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.
Problem
The Shannon capacity of C7 is unknown, motivating improved lower bounds from independent sets in fixed powers of C7.
Method
The authors adapt the independent set {t · (1, 7, 7^2, 7^3, 7^4) | t ∈ Z_382} in C108,382^5 by removing conflicting words and adding new words.
Results
367 vertices in an independent set of C7^5 yield Θ(C7) ≥ 367^1/5 > 3.2578.
Takeaways & Limitations
The construction improves the previously known lower bound Θ(C7) ≥ 350^1/5 > 3.2271.
Takeaways & Limitations
The circular-graph independent set does not translate directly to C7^5 because 382/108 > 7/2.
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).
- 1 Introduction: 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.
- 1 Introduction: 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.
- 1 Introduction: 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.
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.
- Definitions: 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.
- 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.
- 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.
- 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.
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.
- 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.
- 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.
- 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.
- 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).
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.
- The appendix identifies this independent set as the set R from Section 3.