pith. sign in

arxiv: 0809.3725 · v1 · submitted 2008-09-22 · 🧮 math.CO

Near universal cycles for subsets exist

classification 🧮 math.CO
keywords existucycleappearseveryoncepackingssubsetucycles
0
0 comments X
read the original abstract

Let S be a cyclic n-ary sequence. We say that S is a {\it 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.