CAGS: Universal Partial Cycles

Speaker:  Rachel Kirsch, George Mason University 

Title:  Universal Partial Cycles 

Abstract:  

A De Bruijn cycle is a cyclic sequence of symbols that contains each word of

length n  exactly once. A universal partial cycle, or upcycle, covers each word of

length n  exactly once, even more compactly, using a “do not know" symbol that

covers every letter of the alphabet. Upcycles have highly constrained structure

and seem to be rare. Previously it was not known whether any upcycles existed

for n > 4. We present several examples of upcycles with n= 8. We then

present novel approaches to constructing new upcycles from old ones, so that

each of these new examples generates an infinite family of upcycles. At the same

time, we find that upcycles are more structurally constrained than previously

known and satisfy certain pseudorandomness properties, and we prove new

nonexistence results.

This talk is based on joint work with Bennet Goeckner, Corbin Groothuis,

Cyrus Hettle, Brian Kell, Pamela Kirkpatrick, and Ryan Solava and joint work

with Dylan Fillmore, Bennet Goeckner, Jasmine Martin, and Daniel McGinnis.

PDF of Abstract

Time: Friday, November 5, 2021, 12:30pm – 1:30pm

Place:  Zoom – https://gmu.zoom.us/j/98845903474