Combinatorics Seminar

Periodic words, common subsequences and frogs

Boris Bukh, Carnegie Melon University

Thursday, July 2nd, 2020
3:00 PM - 4:00 PM
Zoom ID 797681224

The longest common subsequence (LCS) between two random words is poorly understood. At the start of the talk, I will survey what is known about the problem, and present new conjectures. Most of the talk will be devoted to a simpler problem, the LCS between a fixed periodic word and a random word. We will relate it to ``frog dynamics’’, a new interacting particle system similar to PushASEP. Given time, I hope to present a beautiful, but a mysterious connection of the frog dynamics to a random walk on Dyck paths.

Event contact: iosevich at gmail dot com