##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Chris Cox

#### Carnegie Mellon University

## Periodic words, common subsequences and frogs

##### Abstract:

Let $W^{(n)}$ be the $n$-letter word obtained by repeating a fixed word $W$, and let $R_n$ be a random $n$-letter word over the same alphabet. We show several results about the length of the longest common subsequence (LCS) between $W^{(n)}$ and $R_n$; in particular, we show that its expectation is $\gamma_W n-O(\sqrt{n})$ for an efficiently-computable constant $\gamma_W$.\\ This is done by relating the problem to a new interacting particle system, which we dub ``frog dynamics''. In this system, the particles (`frogs') hop over one another in the order given by their labels. Stripped of the labeling, the frog dynamics reduces to a variant of the PushASEP.\\ In the special case when all symbols of $W$ are distinct, we obtain an explicit formula for the constant $\gamma_W$ and a closed-form expression for the stationary distribution of the associated frog dynamics.\\ Froggies on a pond\\ They get scared and hop along\\ Scaring others too.\\ Their erratic gait\\ Gives us tools to calculate\\ LCS of words.\\ (Joint work with Boris Bukh)

Host: Jacques Verstraete

### February 11, 2020

### 1:00 PM

### AP&M 7321

****************************