2013/03/14 by Champlin, Michelle, Godbole, Anant, Tomlinson, Beverly
#05B30 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1303.3323
Universal Cycles, or U-cycles, as originally defined by de Bruijn, are an efficient method to exhibit a large class of combinatorial objects in a compressed fashion, and with no repeats. de Bruijn's theorem states that U-cycles for n letter words on a k letter alphabet exist for all k and n. Much has already been proved about Universal Cycles for a variety of other objects. This work is intended to augment the current research in the area by exhibiting U-cycles for \it complementary classes. Results will be presented that exhibit the existence of U-cycles for class-alternating words such as alternating vowel-consonant (VCVC) words; words with at least one repeated letter (non-injective functions); words with at least one letter of the alphabet missing (functions that are not onto); words that represent illegal tournament rankings; and words that do not constitute "strong" legal computer passwords. As with previous papers pertaining to U-cycles, connectedness proves to be a nontrivial step.