De Bruijn Covering Codes for Rooted Hypergraphs

Details De Bruijn Covering Codes for Rooted Hypergraphs De Bruijn Covering Codes for Rooted Hypergraphs

2005-05-25

arxiv.org/abs/math/0505528v1

Mathematics

Combinatorics

10 pages, no figures

Scientific paper

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, >..., 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 $\log n$ of the lower bound.

Affiliated with

Also associated with

No associations

Rating

De Bruijn Covering Codes for Rooted Hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with De Bruijn Covering Codes for Rooted Hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and De Bruijn Covering Codes for Rooted Hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-641942