Mathematical Sciences Department Colloquium
Chris Wells, Auburn University
Friday, January 24th
12-1pm
Stratton 202
Title: Periodic words, common subsequences and frogs
Suppose you stumble across two words, and you want to know how similar they are.
For instance, maybe you are a spell-checker or a biologist comparing DNA sequences.
One way to measure ``similarity'' is the length of the longest subsequence which appears within both words.
We call this measure the \emph{longest common subsequence} (LCS).
Even if the LCS between two words is large, whether or not this supposed similarity can be explained purely by random chance may be unclear.
This begs the following question raised by Chv\'atal and Sankoff in 1975: what is the expected LCS of two random words of length $n$ (large) which are sampled independently and uniformly from a fixed, finite alphabet?
Despite being 50 years old, we still know essentially nothing!
To simplify, we instead consider the question: what is the expected LCS between a random word and a deterministic, periodic word?
In this case, we can do a whole lot!
We approach this simplified problem by imagining a bunch of frogs hopping around a ring of lily pads trying to escape the clutches of a randomized monster living in the pond!
In this talk, we will discuss these ``frog dynamics'' and their relationship to the LCS problem, outline our major results obtained from their hopping, and discuss future directions, including extensions to other string-comparison metrics such as the Levenshtein distance.
(Based on joint work with Boris Bukh, and also with Joe Briggs, Alex Parker and Coy Schwieder)