×

New lower bounds for the Shannon capacity of odd cycles. (English) Zbl 1367.05160

Summary: The Shannon capacity of a graph \(G\) is defined as \(c(G)=\sup _{d\geq 1}(\alpha (G^d))^{\frac{1}{d}},\) where \(\alpha (G)\) is the independence number of \(G\). The Shannon capacity of the cycle \(C_5\) on 5 vertices was determined by L. Lovász [IEEE Trans. Inf. Theory 25, 1–7 (1979; Zbl 0395.94021)], but the Shannon capacity of a cycle \(C_p\) 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\) and using stochastic search methods, we show that \(\alpha (C_7^5)\geq 350\), \(\alpha (C_{11}^4)\geq 748\), \(\alpha (C_{13}^4)\geq 1534\), and \(\alpha (C_{15}^3)\geq 381\). This leads to improved lower bounds on the Shannon capacity of \(C_7\) and \(C_{15}: c(C_7)\geq 350^{\frac{1}{5}}> 3.2271\) and \(c(C_{15})\geq 381^{\frac{1}{3}}> 7.2495\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
94A24 Coding theorems (Shannon theory)

Citations:

Zbl 0395.94021

Software:

Cliquer
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon N.: On the capacity of digraphs. Eur. J. Comb. 19, 1-5 (1998). · Zbl 0894.05031
[2] Alon N., Orlitsky A.: Repeated communication and Ramsey graphs. IEEE Trans. Inf. Theory 41, 1276-1289 (1995). · Zbl 0831.94003
[3] Ashley J.J., Siegel P.H.: A note on the Shannon capacity of run-length-limited codes. IEEE Trans. Inf. Theory 33, 601-605 (1987). · Zbl 0631.94005
[4] Baumert L.D., McEliece R.J., Rodemich E., Rumsey H.C. Jr., Stanley R., Taylor H.: A combinatorial packing problem. In: Birkhoff G., Hall M. Jr. (eds.) Computers in Algebra and Number Theory. Proceedings of Symposium in Applied Mathematics of the AMS and SIAM, New York, 1970, pp. 97-108. American Mathematical Society, Providence (1971). · Zbl 0252.05016
[5] Bohman T.: A limit theorem for the Shannon capacities of odd cycles I. Proc. Am. Math. Soc. 131, 3559-3569 (2003). · Zbl 1061.94006
[6] Bohman T., Holzman R., Natarajan V.: On the independence numbers of the cubes of odd cycles. Electron. J. Comb. 20(3), P10 (2013). · Zbl 1295.05133
[7] Bomze I.M., Budinich M., Pardalos P.M., Pelillo M.: The maximum clique problem. In: Du D.Z., Pardalos P.M. (eds.) Handbook of Combinatorial Optimization, Supplement, vol. A, pp. 1-74. Kluwer, Dordrecht (1999). · Zbl 1253.90188
[8] Braun M., Östergård P.R.J., Wassermann A.: New lower bounds for binary constant dimension subspace codes. Submitted for publication. · Zbl 1391.51005
[9] Brouwer A.E., Schrijver A.: Uniform hypergraphs. In: Schrijver A. (ed.) Packing and Covering in Combinatorics. Mathematical Centre Tracts No. 106, pp. 39-73. Mathematisch Centrum, Amsterdam (1979).
[10] Feige U.: Randomized graph products, chromatic numbers, and the Lovász \[\vartheta\] ϑ-function, In: Proceedings of 27th Annual ACM Symposium on the Theory of Computing, pp. 635-640. ACM, New York (1995). · Zbl 1058.94517
[11] Frucht R.: On the groups of repeated graphs. Bull. Am. Math. Soc. 55, 418-420 (1949). · Zbl 0034.25801
[12] Haemers W.: An upper bound for the Shannon capacity of a graph. In: Lovász L., Sós V.T. (eds.) Algebraic Methods in Graph Theory. Colloquia Mathematica Societatis János Bolyai, vol. 25, pp. 267-272. Szeged (1978).
[13] Haemers W.: On some problems of Lovász concerning the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 231-232 (1979). · Zbl 0402.94029
[14] Hammack R., Imrich W., Klavžar S.: Handbook of Product Graphs, 2nd edn. CRC, Boca Raton (2011). · Zbl 1283.05001
[15] Kaski P., Östergård P.R.J.: Classification Algorithms for Codes and Designs. Springer, Berlin (2006). · Zbl 1089.05001
[16] Keller O.H.: Über die lückenlose Erfüllung des Raumes mit Würfeln. J. Reine Angew. Math. 163, 231-248 (1930). · JFM 56.1120.01
[17] Knuth D.E.: The sandwich theorem. Electron. J. Comb. 1, A1 (1994). · Zbl 0810.05065
[18] Körner J., Orlitsky A.: Zero-error information theory. IEEE Trans. Inf. Theory 44, 2207-2229 (1998). · Zbl 0932.94019
[19] Lovász L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1-7 (1979). · Zbl 0395.94021
[20] Mathew K.A., Östergård P.R.J., Popa A.: On the Shannon capacity of triangular graphs. Electron. J. Comb. 20(2), P27 (2013). · Zbl 1267.05206
[21] Montemanni R., Smith D.H.: Heuristic algorithms for constructing binary constant weight codes. IEEE Trans. Inf. Theory 55, 4651-4656 (2009). · Zbl 1367.94375
[22] Niskanen S., Östergård P.R.J.: Cliquer User’s Guide (Version 1.0). Technical Report T48, Communications Laboratory, Helsinki University of Technology, Espoo (2003).
[23] Shannon C.E.: The zero-error capacity of a noisy channel. IRE Trans. Inf. Theory 2, 8-19 (1956).
[24] Szegedy M.: A note on the \[\Theta\] Θ number of Lovász and the generalized Delsarte bound. In: Proceedings of 35th Annual Symposium on Foundations of Computer Science, pp. 36-41. IEEE Computer Society, Los Alamitos (1994).
[25] Vesel A., Žerovnik J.: Improved lower bound on the Shannon capacity of \[C_7\] C7. Inf. Process. Lett. 81, 277-282 (2002). · Zbl 1048.94502
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.