TY - JOUR
T1 - DECOMPOSING RANDOM PERMUTATIONS INTO ORDER-ISOMORPHIC SUBPERMUTATIONS
AU - Groenland, Carla
AU - Johnston, Tom
AU - Korandi, Daniel
AU - Roberts, Alexander
AU - Scott, Alex
AU - Tan, Jane
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - permutation patterns
KW - random permutations
KW - twins
UR - http://www.scopus.com/inward/record.url?scp=85166002556&partnerID=8YFLogxK
U2 - 10.1137/22M148029X
DO - 10.1137/22M148029X
M3 - Article
AN - SCOPUS:85166002556
SN - 0895-4801
VL - 37
SP - 1252
EP - 1261
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 2
ER -