Geodesic
On the longest common subsequence of conjugation invariant random permutations
Mohamed Slim Kammoun1
1Université de Lille
The electronic journal of combinatorics, Tome 27 (2020) no. 4

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl DOI arXiv
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. More generally, in the case where the laws of the two permutations are not necessarily the same, we give 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.
DOI : 10.37236/8669
Classification : 60C05, 60B20, 60F05, 05A16, 05A05
Mots-clés : permutation, conjugation invariant, common sub-sequence

Mohamed Slim Kammoun  1

1 Université de Lille 
Mohamed Slim Kammoun. On the longest common subsequence of conjugation invariant random permutations. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/8669
@article{10_37236_8669,
     author = {Mohamed Slim Kammoun},
     title = {On the longest common subsequence of conjugation invariant random permutations},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {4},
     doi = {10.37236/8669},
     zbl = {1468.60016},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8669/}
}
TY  - JOUR
AU  - Mohamed Slim Kammoun
TI  - On the longest common subsequence of conjugation invariant random permutations
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8669/
DO  - 10.37236/8669
ID  - 10_37236_8669
ER  - 
%0 Journal Article
%A Mohamed Slim Kammoun
%T On the longest common subsequence of conjugation invariant random permutations
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/8669/
%R 10.37236/8669
%F 10_37236_8669

Cité par Sources :