Tight multiple twins in permutations

DOI10.1007/S00026-021-00559-YzbMATH Open1479.05005arXiv2105.02591OpenAlexW3210340505MaRDI QIDQ825967FDOQ825967

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

Publication date: 18 December 2021

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

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.

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

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

zbMATH Keywords

random permutation\(r\)-twins

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• The probabilistic method
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Variations on twins in permutations
• On square-free permutations
• Order-isomorphic twins in permutations

Cited In (8)

• On weak twins and up-and-down subpermutations
• Order-isomorphic twins in permutations
• Variations on twins in permutations
• Title not available (Why is that?)
• Long twins in random words
• 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

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)