De Bruijn sequence constructions

A de Bruijn sequence is a binary string of length 2^n that when considered cyclicly contains every binary string of length $n$ as a substring.  For example 0000100110101111 is a de Bruijn sequence for n=4.  It is well-known that each de Bruijn sequence is in 1-1 correspondence with an Euler cycle in a related de Bruijn graph.  However, because the graph is exponential in size, there has been extensive research into the discovery of simple and efficient constructions for an arbitrary $n$.  In this seminar we will discuss the state of the art with respect to de Bruijn sequence constructions at a level that will be accessible to a broad audience.  Approaches will include:  greedy algorithms, feedback shift registers, successor-rules, and (necklace) concatenation approaches. De Bruijn sequences have properties that are desirable for pseudo-random number generation, and the de Bruijn graph has found application in genome assembly.  These sequences can also be generalized to a larger alphabet, and even considered in two dimensions on the torus.

Contact Person: Zsuzsanna Lipták