Name
Abstract | ||
|---|---|---|
The Shannon capacity of a graph G is defined as $$c(G)=\\sup _{d\\ge 1}(\\alpha (G^d))^{\\frac{1}{d}},$$c(G)=supdź1(ź(Gd))1d, where $$\\alpha (G)$$ź(G) is the independence number of G. The Shannon capacity of the cycle $$C_5$$C5 on 5 vertices was determined by Lovász in 1979, but the Shannon capacity of a cycle $$C_p$$Cp for general odd p remains one of the most notorious open problems in information theory. By prescribing stabilizers for the independent sets in $$C_p^d$$Cpd and using stochastic search methods, we show that $$\\alpha (C_7^5)\\ge 350$$ź(C75)ź350, $$\\alpha (C_{11}^4)\\ge 748$$ź(C114)ź748, $$\\alpha (C_{13}^4)\\ge 1534$$ź(C134)ź1534, and $$\\alpha (C_{15}^3)\\ge 381$$ź(C153)ź381. This leads to improved lower bounds on the Shannon capacity of $$C_7$$C7 and $$C_{15}$$C15: $$c(C_7)\\ge 350^{\\frac{1}{5}} 3.2271$$c(C7)ź350153.2271 and $$c(C_{15})\\ge 381^{\\frac{1}{3}} 7.2495$$c(C15)ź381137.2495. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s10623-016-0194-7 | Des. Codes Cryptography |
Keywords | Field | DocType |
Cube packing,Independent set,Shannon capacity,Zero-error capacity,05C69,94A24 | Discrete mathematics,Combinatorics,Independence number,Vertex (geometry),Shannon capacity of a graph,Independent set,Channel capacity,Mathematics | Journal |
Volume | Issue | ISSN |
abs/1504.01472 | 1-2 | 0925-1022 |
Citations | PageRank | References |
1 | 0.39 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| K. Ashik Mathew | 1 | 12 | 1.75 |
| Patric R. J. Östergård | 2 | 1 | 0.39 |