Event Details

Longest Common Subsequence of Random Permutations

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 √n. This problem is related to the Ulam-Hammersley problem. We recall the classical results for the uniform case as well as partial answers for the conjugation invariant case.