Near-Universal Cycles for Subsets Exist

Dawn Curtis, Taylor Hines, Glenn Hurlbert, Tatiana Moyer

SIAM Journal on Discrete Mathematics · 2009 · 16 citations · 3 references

Concepts

Abstract

Let S be a cyclic n-ary sequence. We say that S is a universal cycle ($(n,k)$-Ucycle) for k-subsets of $[n]$ if every such subset appears exactly once contiguously in S, and is a Ucycle packing if every such subset appears at most once. Few examples of Ucycles are known to exist, so the relaxation to packings merits investigation. A family $\{S_n\}$ of $(n,k)$-Ucycle packings for fixed k is a near-Ucycle if the length of $S_n$ is $(1-o(1))\binom{n}{k}$. In this paper we prove that near-$(n,k)$-Ucycles exist for all k.

References

3