Constructions of asymptotically shortest k-radius sequences

Details Constructions of asymptotically shortest k-radius sequences Constructions of asymptotically shortest k-radius sequences

2011-05-03

arxiv.org/abs/1105.0654v2

Mathematics

Combinatorics

22 pages; replaced an earlier version with a minor typo on page 2

Scientific paper

Let k be a positive integer. A sequence s over an n-element alphabet A is called a k-radius sequence if every two symbols from A occur in s at distance of at most k. Let f_k(n) denote the length of a shortest k-radius sequence over A. We provide constructions demonstrating that (1) for every fixed k and for every fixed e>0, f_k(n) = n^2/(2k) +O(n^(1+e)) and (2) for every k, where k is the integer part of n^a for some fixed real a such that 0 < a <1, f_k(n) = n^2/(2k) +O(n^b), for some b <2-a. Since f_k(n) >= n^2/(2k) - n/(2k), the constructions give asymptotically optimal k-radius sequences. Finally, (3) we construct optimal 2-radius sequences for a 2p-element alphabet, where p is a prime.

Affiliated with

Also associated with

No associations

Rating

Constructions of asymptotically shortest k-radius sequences 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 Constructions of asymptotically shortest k-radius sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructions of asymptotically shortest k-radius sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-694556