Two permutations σ and π are k-similar if they can be decomposed into subpermutations σ(1), . . . , σ(k) and π(1), . . . , π(k) such that σ(i) is order-isomorphic to π(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.

Joint work with Carla Groenland, Tom Johnston, Dániel Korándi, Alexander Roberts and Jane Tan.