DMS Combinatorics Seminar

Speaker: Chris Wells (Auburn University)

Title: An unfroggettable tale of longest common subsequences

Abstract:Suppose you stumble across two words and want to know how similar they are. For instance, maybe you are a spell-checker or a biologist wanting to compare two DNA sequences. One of the simplest ways to measure similarity is the length of the longest common subsequence (LCS) between the words. Even if the LCS between two words is large, it may be unclear whether this supposed similarity can be explained purely by random chance. This begs the following question raised by Chvátal and Sankoff in 1975: what is the expected LCS between two words of length \(n\) (large) which are sampled independently and uniformly from a fixed alphabet? Despite being 50 years old, we essentially know nothing about this question (even in the case of the binary alphabet)!

To simplify the question, we instead consider the LCS between a random word and a deterministic, periodic word. In this case, we can do a whole lot more!  We approach this simplified question 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 depths of 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)