On the longest common subsequence of conjugation invariant random permutations (Q2205121)

This paper studies the longest common sub-sequence of conjugation invariant random permutations. Let \(LCS(\sigma_n,\rho_n)\) be the length of the longest common sub-sequence of the two permutation \(\sigma_n\) and \(\rho_n\) over \(n\) letters. Suppose \(\sigma_n\) and \(\rho_n\) are independent and conjugation invariant. It is shown \(\liminf_{n\rightarrow\infty}\) \(E(LCS(\sigma_n,\rho_n))/\sqrt{n}\ge2\sqrt{\theta}\approx0.564\), where \(\theta\) is the unique solution of \(G(2\sqrt{x})=(2+x)/12\), \(G(x)=\int_{-1}^1(\Omega(s)-|s+x/2|-x/2)_+ds\), and \(\Omega(s)=(\frac{2}{\pi})(s\arcsin(s)+\sqrt{1-s^2})\) if \(|s|<1\), otherwise \(\Omega(s)=|s|\).