Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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 $k$ goes to infinity of $ k + 1/2 - \Theta( C_{2k+1} ) $ is zero, where $ \Theta(G) $is the Shannon capacity of a graph $G$. 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.


References [Enhancements On Off] (What's this?)

  • 1. N. Alon, Graph Powers, Contemporary Combinatorics (B. Bollobás, ed.), Bolyai Society Mathematical Studies, Springer 2002, pp. 11-28. MR 2003h:05181
  • 2. L. Baumert, R. McEliece, E. Rodemich, H. Rumsey, R. Stanley, H. Taylor, A Combinatorial Packing Problem, Computers in Algebra and Number Theory, SIAM-AMS Proc., vol. 4, Providence, American Mathematical Society; 1971, pp. 97-108. MR 49:2437
  • 3. C. Berge, Motivations and history of some of my conjectures Discrete Mathematics 165 (1997), 61-70. MR 98a:05091
  • 4. T. Bohman, A limit theorem for the Shannon capacities of odd cycles I, Proceedings of the AMS 131 (2003), 3559-3569.
  • 5. T. Bohman, R. Holzman, A nontrivial lower bound on the Shannon capacities of the complements of odd cycles, IEEE Transactions on Information Theory, 49(3) (2003), 721-722. MR 2004b:94039
  • 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, Journal of Combinatorial Theory - B, 15 (1973), 146-155. MR 48:177
  • 9. J. Körner and A. Orlitsky, Zero-error information theory, IEEE Transactions on Information Theory 44(6) (1998), 2207-2229. MR 99h:94034
  • 10. L. Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information Theory 25(1) (1979), 1-7. MR 81g:05095
  • 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

Similar Articles

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

American Mathematical Society