A limit theorem for the Shannon capacities of odd cycles I

Author:
Tom Bohman

Journal:
Proc. Amer. Math. Soc. **131** (2003), 3559-3569

MSC (2000):
Primary 94A15, 05C35, 05C38

DOI:
https://doi.org/10.1090/S0002-9939-03-06495-5

Published electronically:
June 5, 2003

MathSciNet review:
1991769

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper contains a construction for independent sets in the powers of odd cycles. It follows from this construction that the limit as goes to infinity of is zero, where is the Shannon capacity of the graph .

**1.**N. Alon, The Shannon capacity of a union,*Combinatorica*, 18 (1998), 301-310. MR**2000i:05096****2.**L. Baumert, R. McEliece, E. Rodemich, H. Rumsey, R. Stanley, and H. Taylor, A Combinatorial Packing Problem,*Computers in Algebra and Number Theory*, American Mathematical Society, Providence, RI, 1971, pp. 97-108. MR**49:2437****3.**C. Berge,*Balanced hypergraphs and some applications to graph theory. A survey of combinatorial theory,*North-Holland, Amsterdam and London, 1973. MR**51:2970****4.**T. Bohman, M. Ruszinkó, and L. Thoma, Shannon capacity of large odd cycles,*Proceedings of the 2000 IEEE International Symposium on Information Theory*, June 25-30, Sorrento, Italy, p. 179.**5.**W. Haemers, On some problems of Lovász concerning the Shannon capacity of a graph,*IEEE Transactions on Information Theory*, 25(2) (1979), 231-232. MR**80g:94040****6.**W. Haemers, An upper bound for the Shannon capacity of a graph,*Colloquia Mathematica Societatis János Bolyai, 25: Algebraic Methods in Graph Theory,*Szeged (Hungary), 1978, 267-272. MR**83m:05098****7.**R. S. Hales, Numerical invariants and the strong product of graphs,*Journal of Combinatorial Theory - B*, 15 (1973), 146-155. MR**48:177****8.**J. Körner and A. Orlitsky, Zero-error information theory,*IEEE Transactions on Information Theory*44(6) (1998), 2207-2229. MR**99h:94034****9.**L. Lovász, On the Shannon capacity of a graph,*IEEE Transactions on Information Theory*25(1) (1979), 1-7. MR**81g:05095****10.**R. J. McEliece, E. R. Rodemich, and H. C. Rumsey, The Lovász bound and some generalizations,*Journal of Combinatorics, Information and Systems Science*3 (1978), 134-152. MR**80a:05168****11.**M. Rosenfeld, On a problem of C. E. Shannon in graph theory,*Proceedings of the American Mathematical Society*, 18 (1967), 315-319. MR**34:7405****12.**C. E. Shannon, The zero-error capacity of a noisy channel,*Institute of Radio Engineers Transactions on Information Theory*, 2(3) (1956), 8-19. MR**19:623b**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2000):
94A15,
05C35,
05C38

Retrieve articles in all journals with MSC (2000): 94A15, 05C35, 05C38

Additional Information

**Tom Bohman**

Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Address at time of publication:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Email:
tbohman@moser.math.cmu.edu

DOI:
https://doi.org/10.1090/S0002-9939-03-06495-5

Keywords:
Shannon capacity,
odd cycles

Received by editor(s):
May 17, 2000

Received by editor(s) in revised form:
June 21, 2000, and September 18, 2001

Published electronically:
June 5, 2003

Additional Notes:
This research was supported in part by NSF Grant DMS-9627408

While this paper was on its way to press, the author discovered A combinatorial packing problem, by L. Baumert et al., 1971, which contains an idea that yields an alternate (and shorter) proof of Theorem 1.1. The shorter proof together with some observations and questions that arise from comparing the two ideas are treated in the forth-coming manuscript A limit theorem for the Shannon capacities of odd cycles II

Communicated by:
John R. Stembridge

Article copyright:
© Copyright 2003
American Mathematical Society