Main content

Novel universal cycle constructions for a variety of combinatorial objects

Show full item record

Title: Novel universal cycle constructions for a variety of combinatorial objects
Author: Wong, Chi Him
Department: School of Computer Science
Program: Computer Science
Advisor: Sawada, Joe
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.
URI: http://hdl.handle.net/10214/8812
Date: 2015-04
Terms of Use: All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.


Files in this item

Files Size Format View
Wong_ChiHim_201505_PhD.pdf 1.045Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record