Tight multiple twins in permutations

DOI10.1007/S00026-021-00559-YMaRDI QIDQ825967zbMATH OpenOpenAlexFDO

Authors Andrzej Dudek, Andrzej Ruciński, Jarosław Grytczuk

Publication date 18 December 2021

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.02591

zbMATH Keywords

random permutation\(r\)-twins

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: Two permutations are similar if they have the same length and the same relative order. A collection of $rge2$ disjoint, similar subsequences of a permutation $pi$ form $r$-twins in $pi$. We study the longest guaranteed length of $r$-twins which are tight in the sense that either each twin alone forms a block or their union does. We address the same question with respect to a random permutation.

Recommendations

• Order-isomorphic twins in permutations
• Variations on twins in permutations
• On weak twins and up-and-down subpermutations
• On weak twins and up-and-down sub-permutations
• Twins in words and long common subsequences in permutations

Cites work

• scientific article; zbMATH DE number 2127722 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• On square-free permutations
• Order-isomorphic twins in permutations
• The probabilistic method
• Variations on twins in permutations

Cited in

(8)

• scientific article; zbMATH DE number 7771747 (Why is no real title available?)
• Long twins in random words
• Variations on twins in permutations
• Order-isomorphic twins in permutations
• On weak twins and up-and-down sub-permutations
• Twins in words and long common subsequences in permutations
• Decomposing Random Permutations into Order-Isomorphic Subpermutations
• On weak twins and up-and-down subpermutations

This page was built for publication: Tight multiple twins in permutations

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