Decomposing random permutations into order-isomorphic subpermutations
<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 &sigma...
| Main Authors: | , , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2023
|
| _version_ | 1797110234271973376 |
|---|---|
| author | Groenland, C Johnston, T Korandi, D Roberts, A Scott, A Tan, J |
| author_facet | Groenland, C Johnston, T Korandi, D Roberts, A Scott, A Tan, J |
| author_sort | Groenland, C |
| collection | OXFORD |
| description | <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> |
| first_indexed | 2024-03-07T07:52:13Z |
| format | Journal article |
| id | oxford-uuid:de6e9e39-a0db-46e4-a983-a76adb505989 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:52:13Z |
| publishDate | 2023 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:de6e9e39-a0db-46e4-a983-a76adb5059892023-07-19T08:10:27ZDecomposing random permutations into order-isomorphic subpermutationsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:de6e9e39-a0db-46e4-a983-a76adb505989EnglishSymplectic ElementsSociety for Industrial and Applied Mathematics2023Groenland, CJohnston, TKorandi, DRoberts, AScott, ATan, J<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> |
| spellingShingle | Groenland, C Johnston, T Korandi, D Roberts, A Scott, A Tan, J Decomposing random permutations into order-isomorphic subpermutations |
| title | Decomposing random permutations into order-isomorphic subpermutations |
| title_full | Decomposing random permutations into order-isomorphic subpermutations |
| title_fullStr | Decomposing random permutations into order-isomorphic subpermutations |
| title_full_unstemmed | Decomposing random permutations into order-isomorphic subpermutations |
| title_short | Decomposing random permutations into order-isomorphic subpermutations |
| title_sort | decomposing random permutations into order isomorphic subpermutations |
| work_keys_str_mv | AT groenlandc decomposingrandompermutationsintoorderisomorphicsubpermutations AT johnstont decomposingrandompermutationsintoorderisomorphicsubpermutations AT korandid decomposingrandompermutationsintoorderisomorphicsubpermutations AT robertsa decomposingrandompermutationsintoorderisomorphicsubpermutations AT scotta decomposingrandompermutationsintoorderisomorphicsubpermutations AT tanj decomposingrandompermutationsintoorderisomorphicsubpermutations |