2005/05/25 by Joshua Cooper, Joshua N. Cooper, Fan Chung +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05B40 (Secondary) #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #MSC-class: 05D40 (Primary) 68R15 #Probability (math.PR) #math.CO #math.PR #msc:05B40 #msc:05D40 #msc:68R15
paper · pdf · doi:10.48550/arxiv.math/0505528
10 pages, no figures
arxiv created 2005/05/25 · openalex publication_date 2005/05/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.