×

On the longest common subsequence of conjugation invariant random permutations. (English) Zbl 1468.60016

This paper studies the longest common sub-sequence of conjugation invariant random permutations. Let \(LCS(\sigma_n,\rho_n)\) be the length of the longest common sub-sequence of the two permutation \(\sigma_n\) and \(\rho_n\) over \(n\) letters. Suppose \(\sigma_n\) and \(\rho_n\) are independent and conjugation invariant. It is shown \(\liminf_{n\rightarrow\infty}\) \(E(LCS(\sigma_n,\rho_n))/\sqrt{n}\ge2\sqrt{\theta}\approx0.564\), where \(\theta\) is the unique solution of \(G(2\sqrt{x})=(2+x)/12\), \(G(x)=\int_{-1}^1(\Omega(s)-|s+x/2|-x/2)_+ds\), and \(\Omega(s)=(\frac{2}{\pi})(s\arcsin(s)+\sqrt{1-s^2})\) if \(|s|<1\), otherwise \(\Omega(s)=|s|\).

MSC:

60C05 Combinatorial probability
60B20 Random matrices (probabilistic aspects)
60F05 Central limit and other weak theorems
05A16 Asymptotic enumeration
05A05 Permutations, words, matrices

Software:

DPPy
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. Baik, P. Deift, and K. Johansson. On the distribution of the length of the longest increasing subsequence of random permutations.J. Amer. Math. Soc., 12(4):1119- 1178, 1999. · Zbl 0932.05001
[2] B. Bukh and L. Zhou. Twins in words and long common subsequences in permutations.Israel J. Math., 213(1):183-209, 2016. · Zbl 1354.68213
[3] P. Flajolet and R. Sedgewick.Analytic Combinatorics. Cambridge University Press, 2009. · Zbl 1165.05001
[4] G. Gautier, G. Polito, R. Bardenet, and M. Valko. Dppy: Dpp sampling with python. J. Mach. Learn. Res., 20:180:1-180:7, 2019.
[5] C. Greene. An extension of Schensted’s theorem.Advances in Math., 14:254-265, 1974. · Zbl 0303.05006
[6] C. Houdr´e and ¨U. I¸slak. A central limit theorem for the length of the longest common subsequences in random words.arXiv:1408.1559, 2014.
[7] C. Houdr´e and C. Xu. A note on the expected length of the longest common subsequences of two i.i.d. random permutations.Electron. J. Combin., 25(2):#P2.50, 2018. · Zbl 1391.05010
[8] V. Ivanov and G. Olshanski. Kerov’s central limit theorem for the Plancherel measure on Young diagrams. InSymmetric functions 2001: surveys of developments and perspectives, volume 74 ofNATO Sci. Ser. II Math. Phys. Chem., pages 93-151. Kluwer Acad. Publ., Dordrecht, 2002. · Zbl 1016.05073
[9] M. S. Kammoun. Monotonous subsequences and the descent process of invariant random permutations.Electron. J. Probab., 23:31 pp., 2018. · Zbl 1406.60018
[10] S. Kerov. The asymptotics of interlacing sequences and the growth of continual Young diagrams.Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 205(Differentsial prime naya Geom. Gruppy Li i Mekh. 13):21-29, 179, 1993. · Zbl 0804.33018
[11] S. Kerov. A differential model for the growth of Young diagrams. InProceedings of the St. Petersburg Mathematical Society, Vol. IV, volume 188 ofAmer. Math. Soc. Transl. Ser. 2, pages 111-130. Amer. Math. Soc., Providence, RI, 1999. · Zbl 0929.05090
[12] S. V. Kerov. Transition probabilities of continual Young diagrams and the Markov moment problem.Funktsional. Anal. i Prilozhen., 27(2):32-49, 96, 1993. · Zbl 0808.05098
[13] B. F. Logan and L. A. Shepp. A variational problem for random Young tableaux. Advances in Math., 26(2):206-222, 1977. · Zbl 0363.62068
[14] P.-L. M´eliot. Kerov’s central limit theorem for Schur-Weyl and Gelfand measures (extended abstract). In M. Bousquet-M´elou, M. Wachs, and A. Hultman, editors, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), volume DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) ofDMTCS Proceedings, pages 669-680, Reykjavik, Iceland, 2011. Discrete Mathematics and Theoretical Computer Science. · Zbl 1355.05245
[15] G. d. B. Robinson. On the Representations of the Symmetric Group.Amer. J. Math., 60(3):745-760, 1938. · JFM 64.0070.01
[16] B. E. Sagan.The symmetric group, volume 203 ofGraduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2001. Representations, combinatorial algorithms, and symmetric functions. · Zbl 0964.05070
[17] C. Schensted. Longest increasing and decreasing subsequences.Canad. J. Math., 13:179-191, 1961. · Zbl 0097.25202
[18] S. Sodin. Fluctuations of interlacing sequences.Zurnal matematiceskoj fiziki, analiza, geometrii, 13(4):364-401, Dec 2017. · Zbl 1386.60029
[19] J. Steele.Probability Theory and Combinatorial Optimization. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, 1997. · Zbl 0916.90233
[20] A. M. Vershik and S. V. Kerov. Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux.Dokl. Akad. Nauk SSSR, 233(6):1024-1027, 1977.
[21] A.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.