*********************************** * Princeton Discrete Math Seminar * *********************************** Speaker: Alex Scott (University of Oxford) Thursday 15th September, 3:00 in Fine Hall 224. Title: Decomposing random permutations 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. ---------------------------------- Anyone wishing to be added to or removed from the mailing list should contact Paul Seymour (pds@math.princeton.edu)