Upcoming Events
CAGS: Universal Partial Cycles
Nov 5, 2021, 12:30 - 1:30 PM
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.
Time: Friday, November 5, 2021, 12:30pm – 1:30pm
Place: Zoom – https://gmu.zoom.us/j/98845903474
