De Bruijn Covering Codes for Rooted Hypergraphs
| dc.creator | Cooper, Joshua N. | |
| dc.creator | Chung, Fan | |
| dc.date | 2005-05-25 | |
| dc.date.accessioned | 2026-07-07T05:20:15Z | |
| dc.date.available | 2026-07-07T05:20:15Z | |
| dc.description | 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. | |
| dc.description | 10 pages, no figures | |
| dc.identifier | https://arxiv.org/abs/math/0505528 | |
| dc.identifier | http://arxiv.org/abs/math/0505528 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/75308 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | MSC-class: 05D40 (Primary) 68R15, 05B40 (Secondary) | |
| dc.title | De Bruijn Covering Codes for Rooted Hypergraphs | |
| dc.type | text |