Universal Cycles of Complementary Classes

zbMATH Open1291.68301arXiv1303.3323MaRDI QIDQ5405460

Anant Godbole, Beverly Tomlinson, Michelle Champlin

Publication date: 2 April 2014

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1303.3323

zbMATH Keywords

class-alternating wordsU-cycles

Mathematics Subject Classification ID

Could not fetch data.

Related Items (2)

Title not available (Why is that?) ⋮ Universal Cycles of Discrete Functions

This page was built for publication: Universal Cycles of Complementary Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405460)