Novel universal cycle constructions for a variety of combinatorial objects

Loading...
Thumbnail Image
Date
2015-05-06
Authors
Wong, Chi Him
Journal Title
Journal ISSN
Volume Title
Publisher
University of Guelph
Abstract

The cyclic sequence 0000100110101111 has the unlikely property that the 16 unique binary substrings of length 4 appear exactly once in the sequence as a substring. This sequence is an example of a universal cycle. A universal cycle for an arbitrary set S is a cyclic sequence of length |S| whose substrings of length n encode |S| distinct instances in S. When S is the set of k-ary strings of length n, these sequences are commonly studied under the name de Bruijn sequence. Universal cycles have been studied for a wide variety of combinatorial objects including permutations, partitions, subsets, multisets, labeled graphs, various functions and passwords. The study of universal cycles has a long history with applications including dynamic connections in overlay networks, genomics, software calculation of the ruler function in computer words, and indexing a 1 in a computer word. There are standard proofs to demonstrate the existence of universal cycles for a variety of combinatorial objects; however, only a small number of universal cycles can be constructed efficiently and practically. This thesis provides novel efficient constructions to generate universal cycles for a variety of combinatorial objects. Our research leads to several new results. Firstly, we propose a novel shift rule to construct de Bruijn sequence for length n binary strings. The shift rule provides a simple and efficient successor rule to find the next bit in the de Bruijn sequence and is applicable to all values of n. We then extend the shift rule to construct de Bruijn sequence for k-ary strings of length n. Secondly, we generalize the Fredricksen-Kessler-Maiorana (FKM) construction and Greedy construction to generate universal cycles for a broad class of k-ary strings. We also prove that the universal cycles produced are the lexicographically smallest for the sets. Lastly, we provide the first known efficient construction to generate universal cycles for length n binary strings where the number of 1s range from c to d given 0 <= c < d <= n. We also prove the existence of universal cycles for other combinatorial objects including subsets of passwords and labeled graphs.

Description
Keywords
universal cycle, de Bruijn sequence, combinatorics on words, FKM algorithm, shift rule, necklace prefix algorithm, Gray code, CAT algorithm, Greedy algorithm, successor rule, nonlinear feedback shift register
Citation