Decomposing random permutations
Decomposing random permutations

Alex Scott, University of Oxford
Fine Hall 224
Two permutations σ and π are ksimilar if they can be decomposed into subpermutations σ(1), . . . , σ(k) and π(1), . . . , π(k) such that σ(i) is orderisomorphic 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 ksimilar. 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.