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 I


Author: Tom Bohman
Journal: Proc. Amer. Math. Soc. 131 (2003), 3559-3569
MSC (2000): Primary 94A15, 05C35, 05C38
Published electronically: June 5, 2003
MathSciNet review: 1991769
Full-text PDF Free Access

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


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 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: http://dx.doi.org/10.1090/S0002-9939-03-06495-5
PII: S 0002-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