Decomposing random permutations into order-isomorphic subpermutations

Abstract

Two permutations $s$ and $t$ are $k$-similar if they can be decomposed into subpermutations $s^1,\dots ,s^k$ and $t^1,\dots ,t^k$ such that $s^i$ is order-isomorphic to $t^i$ for all $i$. Recently, Dudek, Grytczuk and Ruciński posed the problem of determining the minimum $k$ for which two permutations chosen independently and uniformly at random are $k$-similar. We show that two such permutations are $O(n^{1/3}{\log }^{11/6}(n))$-similar with high probability, which is tight up to a polylogarithmic factor. Our result also generalises to simultaneous decompositions of multiple permutations.

11 pages, 2 figures