|
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
Posted:
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  goes to infinity of  is zero, where  is the Shannon capacity of a graph  . 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.
- 1.
N.
Alon, Graph powers, Contemporary combinatorics, Bolyai Soc.
Math. Stud., vol. 10, János Bolyai Math. Soc., Budapest, 2002,
pp. 11–28. MR 1919567
(2003h:05181)
- 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. SIAM-AMS Sympos. Appl. Math., New York, 1970),
Amer. Math. Soc., Providence, R.I., 1971, pp. 97–108. SIAM-AMS
Proc., Vol. IV. MR 0337668
(49 #2437)
- 3.
Claude
Berge, Motivations and history of some of my conjectures,
Discrete Math. 165/166 (1997), 61–70. Graphs and
combinatorics (Marseille, 1995). MR 1439260
(98a:05091), http://dx.doi.org/10.1016/S0012-365X(96)00161-6
- 4.
T. Bohman, A limit theorem for the Shannon capacities of odd cycles I, Proceedings of the AMS 131 (2003), 3559-3569.
- 5.
Tom
Bohman and Ron
Holzman, A nontrivial lower bound on the Shannon capacities of the
complements of odd cycles, IEEE Trans. Inform. Theory
49 (2003), no. 3, 721–722. MR 1967195
(2004b:94039), http://dx.doi.org/10.1109/TIT.2002.808128
- 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, J. Combinatorial Theory Ser. B 15 (1973),
146–155. MR 0321810
(48 #177)
- 9.
János
Körner and Alon
Orlitsky, Zero-error 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
- 10.
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
- 11.
Claude
E. Shannon, The zero error capacity of a noisy channel,
Institute of Radio Engineers, Transactions on Information Theory,
IT-2 (1956), no. September, 8–19. MR 0089131
(19,623b)
- 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:
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
Posted:
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
|
