Seminars & Colloquia
"A potpourri of generalized De Bruijn sequences"
Monday April 14, 2014 11:00 AM
Location: 3211, EBII NCSU Centennial Campus
(Visitor parking instructions)
This talk is part of the Theory Seminar Series
The sequence 11101000 codes the set of eight binary three letter strings in the most compact way possible, since, when written in a cycle, each three bit string can be seen to occur exactly once as a contiguous sequence. This is an example of a de Bruijn cycle.
Generalizations of de Bruijn sequences often involve one or more of of the following:
(i) Changing the rules, e.g., allowing for non-consecutive windows (overlap-cycles) or introducing larger alphabets when smaller ones do not suffice;
(ii) Changing the customary coding, e.g., encoding subsets with their characteristic vectors rather than their elements;
(iii) Introducing non-standard objects for which to exhibit de Bruijn cycles, e.g., words with restrictions, lattice paths, subsets of sizes in a range; words with weights in a range; poset-allocations, etc.
This talk will focus on results that use standard methods to exhibit existence of de Bruijn cycles in each of the above three categories.
Dr. Godbole is a Professor in the Department of Mathematics and Statistics at East Tennessee State University. His research interests are in probability theory and combinatorics, including Discrete Random Structures, Random Graph Theory, Population Genetics, Poisson Approximation, Reliability Theory, Extremal Combinatorics, Probability Inequalities, Statistical Tests for Randomness, and the Interface between Math Research and Math Education. Dr. Godbole has been running a Mathematics REU at ETSU since 1991.
Host: Blair D. Sullivan, Computer Science, NCSU