On Universal Cycles for new Classes of Combinatorial Structures

2010/08/13 by Blanca, Antonio, Godbole, Anant P.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1008.2251

Abstract

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, matroids, restricted multisets, chains of subsets, multichains, 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 Σ, which contain all characters from R ⊂ Σ. Using this result we provide u-cycles for encodings of Sperner families of size 2 and proper chains of subsets.

Related

• Universal and Overlap Cycles for Posets, Words, and Juggling Patterns
• Universal Cycles of Complementary Classes
• On a family of universal cycles for multi-dimensional permutations
• Universal Cycles of Restricted Words
• The Existence and Structure of Universal Partial Cycles