Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
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

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

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia