A note on the expected length of the longest common subsequences of two i.i.d. random permutations. (English) Zbl 1391.05010
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.
References:
| [1] | Paul Beame and Dang-Trinh Huynh-Ngoc.On the value of multiple read/write streams for approximating frequency moments. In Foundations of Computer Science, 2008. FOCS’08. IEEE 49th Annual IEEE Symposium on, pages 499-508. IEEE, 2008. the electronic journal of combinatorics 25(2) (2018), #P2.50 9 |
| [2] | Boris Bukh and Lidong Zhou. Twins in words and long common subsequences in permutations. Israel Journal of Mathematics, 213(1):183-209, 2016. · Zbl 1354.68213 |
| [3] | Christian Houdr´e and ¨Umit I¸slak. A central limit theorem for the length of the longest common subsequence in random words.arXiv:1408.1559v4, 2017. |
| [4] | Shaiy Pilpel. Descending subsequences of random permutations. Journal of Combi natorial Theory, Series A, 53(1):96-116, 1990. · Zbl 0694.05004 |
| [5] | Dan Romik. The surprising mathematics of longest increasing subsequences, vol ume 4. Cambridge University Press, 2015. the electronic journal of combinatorics 25(2) (2018), #P2.50 1 · Zbl 1345.05003 |
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.
