PhD Thesis Defence – Dennis Wong

PhD candidate Dennis Wong will defend his thesis "Novel Universal Cycle Constructions for a Variety of Combinatorial Objects" on April 13, 2015, at 9:00pm in Reynolds 219.

Title

Novel Universal Cycle Constructions for a Variety of Combinatorial Objects

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 such as the design of Sanskrit memory wheels, random number generation, 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 (using polynomial time and space). 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. Unlike the feedback shift register approach, the shift rule 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 well-known 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 a universal cycle for weight-range binary strings. We also extend the construction to generate universal cycles for other combinatorial objects including passwords and labeled graphs.

Advisors: Joseph Sawada