  Bukh and Zhou conjectured that the expectation of the length of the longest
common subsequence of two i.i.d random permutations of size $n$ is greater than
$\sqrt{n}$. We prove in this paper that there exists a universal constant $n_1$
such that their conjecture is satisfied for any pair of i.i.d random
permutations of size greater than $n_1$ with distribution invariant under
conjugation.
  We prove also that asymptotically, this expectation is at least of order
$2\sqrt{n}$ which is the asymptotic behaviour of the uniform setting. More
generally, in the case where the laws of the two permutations are not
necessarily the same, we gibe a lower bound for the expectation. In particular,
we prove that if one of the permutations is invariant under conjugation and
with a good control of the expectation of the number of its cycles, the
limiting fluctuations of the length of the longest common subsequence are of
Tracy-Widom type. This result holds independently of the law of the second
permutation.
