SIAM Journal on Discrete Mathematics · 2011 · 16 citations · 8 references
Natural SciencesComputer ScienceMathematicsCombinatoricsDiscrete MathematicsSet TheoryAlgebraic CombinatoricsCombinatorial EnumerationCombinatorial Set TheoryEnumerative CombinatoricsChainsCombinatorial LatticesCombinatorial RepresentationsEnumeration Of Combinatorial ClassesSperner FamiliesSperner Theory
A universal cycle (u-cycle) is a compact listing of a collection of combinatorial objects. In this paper, we use natural encodings of these objects to show the existence of u-cycles for collections of subsets, restricted multisets, and lattice paths. For subsets, we show that a u-cycle exists for the k-subsets of an n-set if we let k vary in a non zero length interval. We use this result to construct a “covering” of length $(1+o(1))$$n \choose k$ for all subsets of $[n]$ of size exactly k with a specific formula for the $o(1)$ term. We also show that u-cycles exist for all n-length words over some alphabet $\Sigma,$ which contain all characters from $R \subset \Sigma.$ Using this result we provide u-cycles for encodings of Sperner families of size 2 and proper chains of subsets.
8
Universal cycles for combinatorial structures
Fan Chung, Persi Diaconis, Ron Graham · Discrete Mathematics · 1992 · 172 citations
Universal cycles of k-subsets and k-permutations
Brad Jackson · Discrete Mathematics · 1993 · 71 citations
James Oxley · CUBO, A Mathematical Journal · 2003 · 46 citations
Near-Universal Cycles for Subsets Exist
Dawn Curtis, Taylor Hines, Glenn Hurlbert et al. · SIAM Journal on Discrete Mathematics · 2009 · 16 citations