Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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
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?)


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: http://dx.doi.org/10.1090/S0002-9939-04-07470-2
PII: S 0002-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