DECOMPOSING RANDOM PERMUTATIONS INTO ORDER-ISOMORPHIC SUBPERMUTATIONS

Groenland, Carla; Johnston, Tom; Korandi, Daniel; Roberts, Alexander; Scott, Alex; Tan, Jane

DECOMPOSING RANDOM PERMUTATIONS INTO ORDER-ISOMORPHIC SUBPERMUTATIONS

Journal article (2023)

Authors

Carla Groenland Universiteit Utrecht, Discrete Mathematics and Optimization

Tom Johnston University of Bristol

Daniel Korandi University of Oxford

Alexander Roberts University of Oxford

Alex Scott University of Oxford

Jane Tan University of Oxford

Affiliation

External organisation

Permutation patterns Random permutations Twins

To reference this document use:

http://resolver.tudelft.nl/uuid:325a6760-c084-493c-8c9e-6e7b01cf89f3

More Info

expand_more

Published Date

2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

Abstract

Two permutations σ and π are ℓ-similar if they can be decomposed into subpermutations σ(1), . . . ,σ(ℓ) and π(1), . . . ,π(ℓ) such that σ(i) is order-isomorphic to π(i) for all i ∈[ℓ]. Recently, Dudek, Grytczuk, and Ruciński Variations on twins in permutations, Electron. J. Combin., 28 (2021), P3.19. posed the problem of determining the minimum ℓ for which two permutations chosen independently and uniformly at random are ℓ-similar. We show that two such permutations are O(n1/3 log11/6(n))-similar with high probability, which is tight up to a polylogarithmic factor. Our result also generalizes to simultaneous decompositions of multiple permutations.

No files available

Metadata only record. There are no files for this journal article.