Decomposing random permutations into order-isomorphic subpermutations - Groenland, C; Johnston, T; Korandi, D; Roberts, A; Scott, A; Tan, J (Society for Industrial and Applied Mathematics, 2023)
Two permutations σ and π are ℓ-similar if they can be decomposed into subpermutations σ(1), . . . , σ(ℓ) and π(1), . . . , π(ℓ) such that σ(i) is orderisomorphic to π(i) for all i ∈ [ℓ]. Recently, Dudek, Grytczuk and Ruciński 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 generalises to simultaneous decompositions of multiple permutations.