A limit theorem for the Shannon capacities of odd cycles I
Author:
Tom Bohman
Journal:
Proc. Amer. Math. Soc. 131 (2003), 35593569
MSC (2000):
Primary 94A15, 05C35, 05C38
Published electronically:
June 5, 2003
MathSciNet review:
1991769
Fulltext 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 goes to infinity of is zero, where is the Shannon capacity of the graph .
 1.
Noga
Alon, The Shannon capacity of a union, Combinatorica
18 (1998), no. 3, 301–310. MR 1721946
(2000i:05096), http://dx.doi.org/10.1007/PL00009824
 2.
L.
D. Baumert, R.
J. McEliece, Eugene
Rodemich, Howard
C. Rumsey Jr., Richard
Stanley, and Herbert
Taylor, A combinatorial packing problem, Computers in algebra
and number theory (Proc. SIAMAMS Sympos. Appl. Math., New York, 1970),
Amer. Math. Soc., Providence, R.I., 1971, pp. 97–108. SIAMAMS
Proc., Vol. IV. MR 0337668
(49 #2437)
 3.
Claude
Berge, Balanced hypergraphs and some applications to graph
theory, A survey of combinatorial theory (Proc. Internat. Sympos.,
Colorado State Univ., Fort Collins, Colo., 1971), NorthHolland,
Amsterdam, 1973, pp. 15–23. MR 0366723
(51 #2970)
 4.
T. Bohman, M. Ruszinkó, and L. Thoma, Shannon capacity of large odd cycles, Proceedings of the 2000 IEEE International Symposium on Information Theory, June 2530, Sorrento, Italy, p. 179.
 5.
Willem
Haemers, On some problems of Lovász concerning the Shannon
capacity of a graph, IEEE Trans. Inform. Theory 25
(1979), no. 2, 231–232. MR 521317
(80g:94040), http://dx.doi.org/10.1109/TIT.1979.1056027
 6.
W.
Haemers, An upper bound for the Shannon capacity of a graph,
Algebraic methods in graph theory, Vol. I, II (Szeged, 1978) Colloq.
Math. Soc. János Bolyai, vol. 25, NorthHolland, Amsterdam,
1981, pp. 267–272. MR 642046
(83m:05098)
 7.
R.
S. Hales, Numerical invariants and the strong product of
graphs, J. Combinatorial Theory Ser. B 15 (1973),
146–155. MR 0321810
(48 #177)
 8.
János
Körner and Alon
Orlitsky, Zeroerror information theory, IEEE Trans. Inform.
Theory 44 (1998), no. 6, 2207–2229. Information
theory: 1948–1998. MR 1658803
(99h:94034), http://dx.doi.org/10.1109/18.720537
 9.
László
Lovász, On the Shannon capacity of a graph, IEEE Trans.
Inform. Theory 25 (1979), no. 1, 1–7. MR 514926
(81g:05095), http://dx.doi.org/10.1109/TIT.1979.1055985
 10.
R.
J. McEliece, E.
R. Rodemich, and H.
C. Rumsey Jr., The Lovász bound and some
generalizations, J. Combin. Inform. System Sci. 3
(1978), no. 3, 134–152. MR 505587
(80a:05168)
 11.
M.
Rosenfeld, On a problem of C. E. Shannon in graph
theory, Proc. Amer. Math. Soc. 18 (1967), 315–319. MR 0207590
(34 #7405), http://dx.doi.org/10.1090/S00029939196702075903
 12.
Claude
E. Shannon, The zero error capacity of a noisy channel,
Institute of Radio Engineers, Transactions on Information Theory,
IT2 (1956), no. September, 8–19. MR 0089131
(19,623b)
 1.
 N. Alon, The Shannon capacity of a union, Combinatorica, 18 (1998), 301310. MR 2000i:05096
 2.
 L. Baumert, R. McEliece, E. Rodemich, H. Rumsey, R. Stanley, and H. Taylor, A Combinatorial Packing Problem, Computers in Algebra and Number Theory, American Mathematical Society, Providence, RI, 1971, pp. 97108. MR 49:2437
 3.
 C. Berge, Balanced hypergraphs and some applications to graph theory. A survey of combinatorial theory, NorthHolland, Amsterdam and London, 1973. MR 51:2970
 4.
 T. Bohman, M. Ruszinkó, and L. Thoma, Shannon capacity of large odd cycles, Proceedings of the 2000 IEEE International Symposium on Information Theory, June 2530, Sorrento, Italy, p. 179.
 5.
 W. Haemers, On some problems of Lovász concerning the Shannon capacity of a graph, IEEE Transactions on Information Theory, 25(2) (1979), 231232. MR 80g:94040
 6.
 W. Haemers, An upper bound for the Shannon capacity of a graph, Colloquia Mathematica Societatis János Bolyai, 25: Algebraic Methods in Graph Theory, Szeged (Hungary), 1978, 267272. MR 83m:05098
 7.
 R. S. Hales, Numerical invariants and the strong product of graphs, Journal of Combinatorial Theory  B, 15 (1973), 146155. MR 48:177
 8.
 J. Körner and A. Orlitsky, Zeroerror information theory, IEEE Transactions on Information Theory 44(6) (1998), 22072229. MR 99h:94034
 9.
 L. Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information Theory 25(1) (1979), 17. MR 81g:05095
 10.
 R. J. McEliece, E. R. Rodemich, and H. C. Rumsey, The Lovász bound and some generalizations, Journal of Combinatorics, Information and Systems Science 3 (1978), 134152. MR 80a:05168
 11.
 M. Rosenfeld, On a problem of C. E. Shannon in graph theory, Proceedings of the American Mathematical Society, 18 (1967), 315319. MR 34:7405
 12.
 C. E. Shannon, The zeroerror capacity of a noisy channel, Institute of Radio Engineers Transactions on Information Theory, 2(3) (1956), 819. 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 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/S0002993903064955
PII:
S 00029939(03)064955
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 DMS9627408
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 forthcoming manuscript A limit theorem for the Shannon capacities of odd cycles II
Communicated by:
John R. Stembridge
Article copyright:
© Copyright 2003 American Mathematical Society
