A note on the expected length of the longest common subsequences of two i.i.d. random permutations (Q1648658)

Summary: 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,\ldots,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 \(\root 3 \of {n}\) for it.