A note on the expected length of the longest common subsequences of two i.i.d. random permutations

MaRDI QIDQ1648658zbMATH OpenFDO

Authors Christian Houdré, Chen Xu

Publication date 27 June 2018

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

Full work available at URL https://arxiv.org/abs/1703.07691, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p50

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

longest common subsequencerandom permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

Abstract: We address a question and a conjecture on the expected length of the longest common subsequences of two i.i.d.${\displaystyle }$random permutations of $[n]:=1,2,\mathrm{...},n$. The question is resolved by showing that the minimal expectation is not attained in the uniform case. The conjecture asserts that $sqrtn$ is a lower bound on this expectation, but we only obtain $sqrt[3]n$ for it.

Review text

Summary: We address a question and a conjecture on the expected length of the longest common subsequences of two i.i.d. random permutations of \([n]:=\{1,2,\ldots,n\}\). The question is resolved by showing that the minimal expectation is not attained in the uniform case. The conjecture asserts that \(\sqrt{n}\) is a lower bound on this expectation, but we only obtain \(\root 3 \of {n}\) for it.

Recommendations

• On the longest common subsequence of conjugation invariant random permutations
• The rate of convergence of the mean length of the longest common subsequence
• On the longest common pattern contained in two or more random permutations
• On increasing subsequences of random permutations
• LATIN 2004: Theoretical Informatics

Cites work

• Descending subsequences of random permutations
• The surprising mathematics of longest increasing subsequences
• Twins in words and long common subsequences in permutations

Cited in

(7)

• On the longest common subsequence of conjugation invariant random permutations
• Sparse long blocks and the micro-structure of the longuest common subsequences
• A central limit theorem for the length of the longest common subsequences in random words
• Continuously increasing subsequences of random multiset permutations
• On the longest common pattern contained in two or more random permutations
• LATIN 2004: Theoretical Informatics
• Continuously increasing subsequences of random multiset permutations

This page was built for publication: A note on the expected length of the longest common subsequences of two i.i.d. random permutations

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