nach oben

Designs, Codes and Cryptography

Erschienen in:

25.03.2016

New lower bounds for the Shannon capacity of odd cycles

verfasst von: K. Ashik Mathew, Patric R. J. Östergård

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1-2/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Shannon capacity of a graph G is defined as \(c(G)=\sup _{d\ge 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 Lovász in 1979, 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)\ge 350\), \(\alpha (C_{11}^4)\ge 748\), \(\alpha (C_{13}^4)\ge 1534\), and \(\alpha (C_{15}^3)\ge 381\). This leads to improved lower bounds on the Shannon capacity of \(C_7\) and \(C_{15}\): \(c(C_7)\ge 350^{\frac{1}{5}}> 3.2271\) and \(c(C_{15})\ge 381^{\frac{1}{3}}> 7.2495\).

Vorheriger Artikel Light tails and the Hermitian dual polar graphs

Nächster Artikel Relative t-designs in binary Hamming association scheme H(n, 2)

Nur mit Berechtigung zugänglich

Alon N.: On the capacity of digraphs. Eur. J. Comb. 19, 1–5 (1998).

Alon N., Orlitsky A.: Repeated communication and Ramsey graphs. IEEE Trans. Inf. Theory 41, 1276–1289 (1995).

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).

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).

Bohman T.: A limit theorem for the Shannon capacities of odd cycles I. Proc. Am. Math. Soc. 131, 3559–3569 (2003).

Bohman T., Holzman R., Natarajan V.: On the independence numbers of the cubes of odd cycles. Electron. J. Comb. 20(3), P10 (2013).

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).

Braun M., Östergård P.R.J., Wassermann A.: New lower bounds for binary constant dimension subspace codes. Submitted for publication.

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).

11.

Frucht R.: On the groups of repeated graphs. Bull. Am. Math. Soc. 55, 418–420 (1949).

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).

14.

Hammack R., Imrich W., Klavžar S.: Handbook of Product Graphs, 2nd edn. CRC, Boca Raton (2011).

15.

Kaski P., Östergård P.R.J.: Classification Algorithms for Codes and Designs. Springer, Berlin (2006).

16.

Keller O.H.: Über die lückenlose Erfüllung des Raumes mit Würfeln. J. Reine Angew. Math. 163, 231–248 (1930).

17.

Knuth D.E.: The sandwich theorem. Electron. J. Comb. 1, A1 (1994).

18.

Körner J., Orlitsky A.: Zero-error information theory. IEEE Trans. Inf. Theory 44, 2207–2229 (1998).

19.

Lovász L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1–7 (1979).

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).

21.

Montemanni R., Smith D.H.: Heuristic algorithms for constructing binary constant weight codes. IEEE Trans. Inf. Theory 55, 4651–4656 (2009).

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\). Inf. Process. Lett. 81, 277–282 (2002).

Titel: New lower bounds for the Shannon capacity of odd cycles
verfasst von: K. Ashik Mathew
Patric R. J. Östergård
Publikationsdatum: 25.03.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1-2/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-016-0194-7

Springer Professional

New lower bounds for the Shannon capacity of odd cycles

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1-2/2017

Distance mean-regular graphs

Light tails and the Hermitian dual polar graphs

Implementing Brouwer’s database of strongly regular graphs

Relative t-designs in binary Hamming association scheme H(n, 2)

On almost small and almost large super-Vandermonde sets in GF(q)

The uniqueness of a distance-regular graph with intersection array and related results

Premium Partner