Zbigniew Lonc: Constructions of short k-radius sequences

A sequence over a finite alphabet is a k-radius sequence if every two elements of the alphabet are within distance at most k at least once somewhere in the sequence. These sequences were introduced to model a caching strategy for computing certain functions on large data sets. We shall present some constructions of k-radius sequences of asymptotically shortest length. We shall also discuss some generalizations of this problem and its connections to other combinatorial problems such as achromatic and harmonious colorings of graphs and hypergraphs.