Click here for full text:
The Asymptotic Capacity of Multi-Dimensional Runlength-Limited Constraints and Independent Sets in Hypergraphs
Ordentlich, Erik; Roth, Ron M.
HPL-2002-348
Keyword(s): regular graphs; Hamming graphs; linear hypergraphs; multi-dimensional constraints; runlength-limited constraints
Abstract: 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.
12 Pages
Back to Index
| 
printable version
