Math Colloquium

Speaker: Nathan Johnston (Mount Allison University)

Title: The Minimal Superpermutation Problem

Abstract: We discuss the open problem of finding the shortest string on n symbols that contains all permutations of those n symbols as contiguous substrings (for example, in the n = 3 case the string ”123121321” contains each permutation of ”123” as a substring). We present the best known upper and lower bounds on the minimal length of such a string and discuss how those bounds have improved over time, including recent advancements made by an anonymous poster on the ”4chan” internet forum as well as science fiction author Greg Egan.

Time

Starts:
Ends:

Location

Chase Building - Room 319

Cost

No cost

Contact

sara.faridi@dal.ca