printable pdf
比利时vs摩洛哥足彩 ,
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

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