
A limit theorem for the Shannon capacities of odd cycles. II
Author(s) -
Tom Bohman
Publication year - 2004
Publication title -
proceedings of the american mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.968
H-Index - 84
eISSN - 1088-6826
pISSN - 0002-9939
DOI - 10.1090/s0002-9939-04-07470-2
Subject(s) - algorithm , artificial intelligence , computer science
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 k goes to infinity of k + 1 / 2 − Θ ( C 2 k + 1 ) k + 1/2 - \Theta ( C_{2k+1} ) is zero, where Θ ( G ) \Theta (G) is the Shannon capacity of a graph G 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.