Available in electronic format
Available in print format		 Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826 (e) ISSN 0002-9939 (p)

Articles in press | Recently posted articles | Most recent issue | All issues
     

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

Author(s): Tom Bohman
Journal: Proc. Amer. Math. Soc. 133 (2005), 537-543.
MSC (2000): Primary 94A15, 05C35, 05C38
Posted: September 8, 2004
Retrieve article in: PDF

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:

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: 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
Posted: September 8, 2004
Additional Notes: This research was supported in part by NSF Grant DMS-0100400.
Communicated by: John R. Stembridge
Copyright of article: Copyright 2004, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google