A Note on the Expected Length of the Longest Common Subsequences of two i.i.d. Random Permutations
arXiv:1703.07691
Abstract
We address a question and a conjecture on the expected length of the longest common subsequences of two i.i.d.$\ $random permutations of $[n]:=\{1,2,...,n\}$. The question is resolved by showing that the minimal expectation is not attained in the uniform case. The conjecture asserts that $\sqrt{n}$ is a lower bound on this expectation, but we only obtain $\sqrt[3]{n}$ for it.
10 pages. Final version which is to appear in Electronic Journal of Combinatorics