DocumentCode :
3783021
Title :
Shannon capacity of large odd cycles
Author :
T. Bohman;M. Ruszinko;L. Thoma
Author_Institution :
Dept. of Math. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA
fYear :
2000
Firstpage :
179
Abstract :
It is known that lim inf/sub n/spl rarr//spl infin//((2n+1)/2-/spl Theta/(C/sub 2n+1/))=0 and that the lim sup of this difference is at most 1/4, where /spl Theta/(G) is the Shannon (1956) capacity of the graph G. We prove that the above lim sup is at most 1/6 and conjecture that the limit itself exists and equals 0. We show that the lim sup is small by constructing large independent sets in the third power of C/sub 2n+1/.
Keywords :
"Decoding","Information theory","Graph theory"
Publisher :
ieee
Conference_Titel :
Information Theory, 2000. Proceedings. IEEE International Symposium on
Print_ISBN :
0-7803-5857-0
Type :
conf
DOI :
10.1109/ISIT.2000.866474
Filename :
866474
Link To Document :
بازگشت