Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

hp.com home

Technical Reports

printable version

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

Click here for full text: Postscript PDF

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

Ordentlich, Erik; Roth, Ron M.


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

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.