De Bruijn Covering Codes for Rooted Hypergraphs

MaRDI QIDQ6475546zbMATH OpenFDO

Authors Joshua Cooper, Fan Chung

Publication date 25 May 2005

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorics on words (68R15)

Abstract: What is the length of the shortest sequence $S$ of reals so that the set of consecutive $n$-words in $S$ form a covering code for permutations on $1,2,>\mathrm{...},n$ of radius $R$ ? (The distance between two $n$-words is the number of transpositions needed to have the same order type.) The above problem can be viewed as a special case of finding a De Bruijn covering code for a rooted hypergraph. Each edge of a rooted hypergraph contains a special vertex, called the {it root} of the edge, and each vertex is the root of a unique edge, called its {it ball}. A De Bruijn covering code is a subset of the roots such that every vertex is in some edge containing a chosen root. Under some mild conditions, we obtain an upper bound for the shortest length of a De Bruijn covering code of a rooted hypergraph, a bound which is within a factor of $logn$ of the lower bound.

This page was built for publication: De Bruijn Covering Codes for Rooted Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6475546)