A note on the expected length of the longest common subsequences of two i.i.d. random permutations (Q1648658): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Twins in words and long common subsequences in permutations / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Descending subsequences of random permutations / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The Surprising Mathematics of Longest Increasing Subsequences / rank | |||
Normal rank | |||
Latest revision as of 00:49, 16 July 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on the expected length of the longest common subsequences of two i.i.d. random permutations |
scientific article |
Statements
A note on the expected length of the longest common subsequences of two i.i.d. random permutations (English)
0 references
27 June 2018
0 references
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.
0 references
random permutation
0 references
longest common subsequence
0 references
