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

permutationconjugation invariantcommon sub-sequence

Mathematics Subject Classification ID

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

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.

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

• 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?)
• 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
• 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)

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

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)