***********************************
* 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)