Home > Research > Publications & Outputs > On the Longest Common Subsequence of Conjugatio...

Research

Links

Text available via DOI:

  • https://doi.org/10.37236/8669

    Final published version

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

View graph of relations

On the Longest Common Subsequence of Conjugation Invariant Random Permutations

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

On the Longest Common Subsequence of Conjugation Invariant Random Permutations. / Kammoun, Slim.
In: The Electronic Journal of Combinatorics , Vol. 27, No. 4, P4.10, 16.10.2020.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Kammoun, S 2020, 'On the Longest Common Subsequence of Conjugation Invariant Random Permutations', The Electronic Journal of Combinatorics , vol. 27, no. 4, P4.10. https://doi.org/10.37236/8669

APA

Kammoun, S. (2020). On the Longest Common Subsequence of Conjugation Invariant Random Permutations. The Electronic Journal of Combinatorics , 27(4), Article P4.10. https://doi.org/10.37236/8669

Vancouver

Kammoun S. On the Longest Common Subsequence of Conjugation Invariant Random Permutations. The Electronic Journal of Combinatorics . 2020 Oct 16;27(4):P4.10. doi: 10.37236/8669

Author

Kammoun, Slim. / On the Longest Common Subsequence of Conjugation Invariant Random Permutations. In: The Electronic Journal of Combinatorics . 2020 ; Vol. 27, No. 4.

Bibtex

@article{318a42b0bbc4471fad506f6cf1e5a3a1,
title = "On the Longest Common Subsequence of Conjugation Invariant Random Permutations",
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 √n. We prove in this paper that there exists a universal constant n1 such that their conjecture is satisfied for any pair of i.i.d random permutations of size greater than n1 with distribution invariant under conjugation. More generally, in the case where the laws of the two permutations are not necessarily the same, we give 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.",
author = "Slim Kammoun",
year = "2020",
month = oct,
day = "16",
doi = "10.37236/8669",
language = "English",
volume = "27",
journal = "The Electronic Journal of Combinatorics ",
issn = "1077-8926",
publisher = "Electronic Journal of Combinatorics",
number = "4",

}

RIS

TY - JOUR

T1 - On the Longest Common Subsequence of Conjugation Invariant Random Permutations

AU - Kammoun, Slim

PY - 2020/10/16

Y1 - 2020/10/16

N2 - 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 √n. We prove in this paper that there exists a universal constant n1 such that their conjecture is satisfied for any pair of i.i.d random permutations of size greater than n1 with distribution invariant under conjugation. More generally, in the case where the laws of the two permutations are not necessarily the same, we give 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.

AB - 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 √n. We prove in this paper that there exists a universal constant n1 such that their conjecture is satisfied for any pair of i.i.d random permutations of size greater than n1 with distribution invariant under conjugation. More generally, in the case where the laws of the two permutations are not necessarily the same, we give 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.

U2 - 10.37236/8669

DO - 10.37236/8669

M3 - Journal article

VL - 27

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1077-8926

IS - 4

M1 - P4.10

ER -