Near universal cycles for subsets exist

2008/09/22 by Dawn Curtis, Taylor Hines, Curtis, Dawn +5 · 1 citation
Engineering · Mathematics · #05B30 (Primary) 05A05 #05C45 (Secondary) #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05A05 #msc:05B30 #msc:05C45

paper · pdf · doi:10.48550/arxiv.0809.3725

14 pages, 3 figures

arxiv created 2008/09/22 · openalex publication_date 2008/09/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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))\binomnk. In this paper we prove that near-(n,k)-Ucycles exist for all k.

Cited by

• Universal cycle constructions for k-subsets and k-multisets

Related

• Universal and Near-Universal Cycles of Set Partitions
• On Universal Cycles for new Classes of Combinatorial Structures
• Universal cycle constructions for k-subsets and k-multisets
• Universal and Overlap Cycles for Posets, Words, and Juggling Patterns
• Universal Cycles of Complementary Classes