A limit theorem for the Shannon capacities of odd cycles I
HTML articles powered by AMS MathViewer
- by Tom Bohman
- Proc. Amer. Math. Soc. 131 (2003), 3559-3569
- DOI: https://doi.org/10.1090/S0002-9939-03-06495-5
- Published electronically: June 5, 2003
- PDF | Request permission
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
- Noga Alon, The Shannon capacity of a union, Combinatorica 18 (1998), no. 3, 301–310. MR 1721946, DOI 10.1007/PL00009824
- 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) SIAM-AMS Proc., Vol. IV, Amer. Math. Soc., Providence, R.I., 1971, pp. 97–108. MR 0337668
- 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) North-Holland, Amsterdam, 1973, pp. 15–23. MR 0366723
- T. Bohman, M. Ruszinkó, and 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.
- 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, DOI 10.1109/TIT.1979.1056027
- 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, North-Holland, Amsterdam-New York, 1981, pp. 267–272. MR 642046
- R. S. Hales, Numerical invariants and the strong product of graphs, J. Combinatorial Theory Ser. B 15 (1973), 146–155. MR 321810, DOI 10.1016/0095-8956(73)90014-2
- 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, DOI 10.1109/18.720537
- László Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), no. 1, 1–7. MR 514926, DOI 10.1109/TIT.1979.1055985
- 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
- M. Rosenfeld, On a problem of C. E. Shannon in graph theory, Proc. Amer. Math. Soc. 18 (1967), 315–319. MR 207590, DOI 10.1090/S0002-9939-1967-0207590-3
- Saunders MacLane and O. F. G. Schilling, Infinite number fields with Noether ideal theories, Amer. J. Math. 61 (1939), 771–782. MR 19, DOI 10.2307/2371335
Bibliographic 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
- 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
- © Copyright 2003 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 131 (2003), 3559-3569
- MSC (2000): Primary 94A15, 05C35, 05C38
- DOI: https://doi.org/10.1090/S0002-9939-03-06495-5
- MathSciNet review: 1991769