| Summary: | <p>Two permutations σ and π are ℓ-similar if they can be decomposed into subpermutations σ<sup>(1)</sup>, . . . , σ<sup>(ℓ)</sup> and π<sup>(1)</sup>, . . . , π<sup>(ℓ)</sup> such that σ<sup>(i)</sup> is orderisomorphic to π<sup>(i)</sup> for all i ∈ [ℓ]. Recently, Dudek, Grytczuk and Ruciński posed the problem of determining the minimum ℓ for which two permutations chosen independently and uniformly at random are ℓ-similar. We show that two such permutations are <em>O</em>(<em>n</em><sup>1/3</sup> log<sup>11/6</sup> (<em>n</em>))-similar with high probability, which is tight up to a polylogarithmic factor. Our result also generalises to simultaneous decompositions of multiple permutations.</p>
|
|---|