A limit theorem for the Shannon capacities of odd cycles. II
HTML articles powered by AMS MathViewer
- by Tom Bohman PDF
- Proc. Amer. Math. Soc. 133 (2005), 537-543 Request permission
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
- N. Alon, Graph powers, Contemporary combinatorics, Bolyai Soc. Math. Stud., vol. 10, János Bolyai Math. Soc., Budapest, 2002, pp. 11–28. MR 1919567
- 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, Motivations and history of some of my conjectures, Discrete Math. 165/166 (1997), 61–70. Graphs and combinatorics (Marseille, 1995). MR 1439260, DOI 10.1016/S0012-365X(96)00161-6
- T. Bohman, A limit theorem for the Shannon capacities of odd cycles I, Proceedings of the AMS 131 (2003), 3559–3569.
- 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, DOI 10.1109/TIT.2002.808128
- 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.
- M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The Strong Perfect Graph Theorem, submitted.
- 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
- 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
Additional Information
- Tom Bohman
- Affiliation: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
- Email: tbohman@moser.math.cmu.edu
- 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
- © Copyright 2004 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 133 (2005), 537-543
- MSC (2000): Primary 94A15, 05C35, 05C38
- DOI: https://doi.org/10.1090/S0002-9939-04-07470-2
- MathSciNet review: 2093078