2006/08/30 by Tobias Johnson, Tobias L. Johnson, Joshua Zahl +2
Engineering · Mathematics · #05B30 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematics and Applications #graph theory and CDMA systems #math.CO #msc:05B30
paper · pdf · doi:10.48550/arxiv.math/0608769
6 pages
arxiv created 2006/08/30 · openalex publication_date 2006/08/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider the collection of all t-multisets of 1,...,n. A universal cycle on multisets is a string of numbers, each of which is between 1 and n, such that if these numbers are considered in t-sized windows, every multiset in the collection is present in the string precisely once. The problem of finding necessary and sufficient conditions on n and t for the existence of universal cycles and similar combinatorial structures was first addressed by DeBruijn in 1946 (who considered t-tuples instead of t-multisets). The past 15 years has seen a resurgence of interest in this area, primarily due to Chung, Diaconis, and Graham's 1992 paper on the subject. For the case t=3, we determine necessary and sufficient conditions on n for the existence of universal cycles, and we examine how this technique can be generalized to other values of t.