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.
Chase Building - Room 319