A limit theorem for the Shannon capacities of odd cycles. II

Author:
Tom Bohman

Journal:
Proc. Amer. Math. Soc. **133** (2005), 537-543

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

DOI:
https://doi.org/10.1090/S0002-9939-04-07470-2

Published electronically:
September 8, 2004

MathSciNet review:
2093078

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It follows from a construction for independent sets in the powers of odd cycles given in the predecessor of this paper that the limit as goes to infinity of is zero, where is the Shannon capacity of a graph . This paper contains a shorter proof of this limit theorem that is based on an `expansion process' introduced in an older paper of L. Baumert, R. McEliece, E. Rodemich, H. Rumsey, R. Stanley and H. Taylor. We also refute a conjecture from that paper, using ideas from the predecessor of this paper.

**1.**N. Alon,*Graph powers*, Contemporary combinatorics, Bolyai Soc. Math. Stud., vol. 10, János Bolyai Math. Soc., Budapest, 2002, pp. 11–28. MR**1919567****2.**L. D. Baumert, R. J. McEliece, Eugene Rodemich, Howard C. Rumsey Jr., Richard Stanley, and Herbert Taylor,*A combinatorial packing problem*, Computers in algebra and number theory (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1970) Amer. Math. Soc., Providence, R.I., 1971, pp. 97–108. SIAM-AMS Proc., Vol. IV. MR**0337668****3.**Claude Berge,*Motivations and history of some of my conjectures*, Discrete Math.**165/166**(1997), 61–70. Graphs and combinatorics (Marseille, 1995). MR**1439260**, https://doi.org/10.1016/S0012-365X(96)00161-6**4.**T. Bohman, A limit theorem for the Shannon capacities of odd cycles I,*Proceedings of the AMS*131 (2003), 3559-3569.**5.**Tom Bohman and Ron Holzman,*A nontrivial lower bound on the Shannon capacities of the complements of odd cycles*, IEEE Trans. Inform. Theory**49**(2003), no. 3, 721–722. MR**1967195**, https://doi.org/10.1109/TIT.2002.808128**6.**T. Bohman, M. Ruszinkó, 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.**7.**M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The Strong Perfect Graph Theorem, submitted.**8.**R. S. Hales,*Numerical invariants and the strong product of graphs*, J. Combinatorial Theory Ser. B**15**(1973), 146–155. MR**0321810****9.**János Körner and Alon Orlitsky,*Zero-error information theory*, IEEE Trans. Inform. Theory**44**(1998), no. 6, 2207–2229. Information theory: 1948–1998. MR**1658803**, https://doi.org/10.1109/18.720537**10.**László Lovász,*On the Shannon capacity of a graph*, IEEE Trans. Inform. Theory**25**(1979), no. 1, 1–7. MR**514926**, https://doi.org/10.1109/TIT.1979.1055985**11.**C. E. Shannon, The zero-error capacity of a noisy channel,*IRE 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 Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Email:
tbohman@moser.math.cmu.edu

DOI:
https://doi.org/10.1090/S0002-9939-04-07470-2

Keywords:
Shannon capacity,
odd cycles

Received by editor(s):
May 30, 2003

Received by editor(s) in revised form:
August 5, 2003

Published electronically:
September 8, 2004

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

Communicated by:
John R. Stembridge

Article copyright:
© Copyright 2004
American Mathematical Society