The Asymptotic Capacity of Multi-Dimensional Runlength-Limited Constraints and Independent Sets

Ordentlich, Erik ; Roth, Ron M.

HP Development Company

关键词: regular graphs;    Hamming graphs;    linear hypergraphs;    multi-dimensional constraints;    runlength-limited constraints;   

RP-ID  :  HPL-2002-348

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Please Note. This abstract contains mathematical formulae which cannot be represented here. Let C(n,d) be the Shannon capacity of the n-dimensional (d, oo)- runlength-limited (RLL) constraint. Denote by I(n,q) the number of independent sets in the Hamming graph with vertices consisting of all n-tuples over an alphabet of size q and edges connecting pairs of vertices with Hamming distance 1. We show that lim(subscript n)->infinity C(n,d) =lim(subscript n)- >infinity(d+1) (superscript -n) log(subscript 2) I (n, d+1)=1/(d+1). Our method also leads to an improvement of a previous bound by Alon on the number of independent sets in regular graphs and to a generalization of this bound to a family of hypergraphs, of which the Hamming graphs can be thought of as a special case.