On the longest common subsequence of conjugation invariant random permutations

DOI10.37236/8669MaRDI QIDQ2205121zbMATH OpenOpenAlexFDO

Authors Mohamed Slim Kammoun

Publication date 20 October 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1904.00725

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

common sub-sequenceconjugation invariantpermutation

Mathematics Subject Classification ID

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

Abstract: 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 $sqrtn$. 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 $2sqrtn$ 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.

Review text

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|\).

Recommendations

• A note on the expected length of the longest common subsequences of two i.i.d. random permutations
• On the longest common pattern contained in two or more random permutations
• scientific article; zbMATH DE number 1047715
• On the limiting law of the length of the longest common and increasing subsequences in random words
• On the distribution of the length of the longest increasing subsequence of random permutations

Cites work

• A note on the expected length of the longest common subsequences of two i.i.d. random permutations
• A variational problem for random Young tableaux
• An extension of Schensted's theorem
• Analytic combinatorics
• Fluctuations of interlacing sequences
• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 4217861 (Why is no real title available?)
• scientific article; zbMATH DE number 1303717 (Why is no real title available?)
• scientific article; zbMATH DE number 1857665 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Kerov's central limit theorem for Schur-Weyl and Gelfand measures (extended abstract)
• Longest Increasing and Decreasing Subsequences
• Monotonous subsequences and the descent process of invariant random permutations
• On the distribution of the length of the longest increasing subsequence of random permutations
• Transition probabilities for continual Young diagrams and the Markov moment problem
• Twins in words and long common subsequences in permutations

Cited in

(11)

• A note on the expected length of the longest common subsequences of two i.i.d. random permutations
• Monotonous subsequences and the descent process of invariant random permutations
• On rates of convergence for common subsequences and first passage time
• Longest common substring for random subshifts of finite type
• Universality for random permutations and some other groups
• Statistical enumeration of groups by double cosets
• Sparse long blocks and the micro-structure of the longuest common subsequences
• The length of the longest common subsequence of two independent Mallows permutations
• Inversions and longest increasing subsequence for \(k\)-card-minimum random permutations
• On the longest common pattern contained in two or more random permutations
• Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs

Describes a project that uses

Uses Software

• DPPy

This page was built for publication: On the longest common subsequence of conjugation invariant random permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2205121)