Decomposing Random Permutations into Order-Isomorphic Subpermutations

DOI10.1137/22M148029XMaRDI QIDQ6161260zbMATH OpenOpenAlexFDO

Authors Carla Groenland, Tom Johnston, Dániel Korándi, Alexander Roberts, Alex Scott, Jane Tan

Publication date 27 June 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.10789

zbMATH Keywords

permutation patternsrandom permutationstwins

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

Abstract: 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'nski 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}lo{g}^{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.

Recommendations

• Permutations with equal orders
• Tight multiple twins in permutations
• Order-isomorphic twins in permutations
• On weak twins and up-and-down subpermutations
• On weak twins and up-and-down sub-permutations

Cites work

• A simple algorithm for edge-coloring bipartite multigraphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• scientific article; zbMATH DE number 3900797 (Why is no real title available?)
• scientific article; zbMATH DE number 3675942 (Why is no real title available?)
• scientific article; zbMATH DE number 795114 (Why is no real title available?)
• Minimal decompositions of graphs into mutually isomorphic subgraphs
• On the length of the longest monotone subsequence in a random permutation
• On weak twins and up-and-down subpermutations
• Order-isomorphic twins in permutations
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• The height of a random partial order: Concentration of measure
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Tight multiple twins in permutations
• Variations on twins in permutations

Cited in

(1)

• Decomposing labeled interval orders as pairs of permutations

This page was built for publication: Decomposing Random Permutations into Order-Isomorphic Subpermutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161260)