论文标题
将随机排列分解为阶数字子渗透
Decomposing random permutations into order-isomorphic subpermutations
论文作者
论文摘要
两个排列$ s $和$ t $是$ k $ -similar如果可以将它们分解为subpermutations $ s^1，\ ldots，s^k $和$ t^1，\ ldots，t^k $，以便$ s^i $是订单 - iSomorphic to isomorphic to $ t^i $ $ $ $ $ $ $ $ $ $ $。最近，Dudek，Grytczuk和Ruciński提出了一个问题，即确定最低$ K $的最低$ K $，该$ k $的两个排列在随机和均匀的随机选择为$ k $ -sibillial。我们表明，两个这样的排列为$ o（n^{1/3} \ log^{11/6}（n））$ - 与高概率相似，这是紧密的，直至polylogarithmic figinal。我们的结果也概括了多个排列的同时分解。
Two permutations $s$ and $t$ are $k$-similar if they can be decomposed into subpermutations $s^1, \ldots, s^k$ and $t^1, \ldots, t^k$ such that $s^i$ is order-isomorphic to $t^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.
