Length of Longest Common Subsequences of Random Words over Large Alphabets

Consider the length $L$ of the longest common subsequence
(LCS) of two randomly uniformly and independently chosen $n$ character
words over a $k$--ary alphabet.  Subadditivity arguments yield that
$\Ex{L}/n$ converges to a constant $\gamma_k$.  Under suitable
assumptions on $k$ we settle a conjecture of Sankoff and Mainville
from the early 80's claiming that $\gamma_k\sqrt{k} \to 2$ when
$n \to \infty$.

Our work elicits a speculated upon connection between several
probabilistic models of sequence comparison and the behavior of the
celebrated longest increasing sequence (LIS) problem (also known
as Ulam's problem).

The talk will survey results on both the LCS and LIS problem, place
them under a common framework, and focus on the exact asymptotic
results that can be derived. Several natural questions that arise
from stating such framework will be discussed.


Joint work with Martin Loebl (Charles U.) and Jiri Matousek (Charles U.)