Slim Kammoun

Université de Toulouse III (France) Université de Toulouse III (France)


Longest Common Subsequence of Random Permutations


Probability Seminar


10th November 2021, 4:00 pm – 5:00 pm
Fry Building, G.07 (also on zoom)


Bukh and Zhou conjectured that the expectation of the length of the longest common subsequence (LCS) of two i.i.d random permutations of size $n$ is greater than $\sqrt{n}$.

This problem is related to the Ulam-Hammersley problem; Ulam conjectured that the expectation of the length of the longest increasing subsection (LIS) for a uniform permutation behaves like $c\sqrt{n}$. The conjecture was solved in 1977, but few results are known for non-uniform permutations. The LIS and LCS are closely related, and solving the conjecture of Bukh and Zhou is equivalent to minimize the expected value of LIS for random permutations that can be written as $\rho_n\circ\sigma_n^{-1}$ where $\sigma_n$ and $\rho_n$ are i.i.d. random permutations.

We recall the classical results for the uniform case as well as partial answers for the conjugation invariant case.






Comments are closed.
css.php