Permutations with fixed pattern densities

DOI10.1002/RSA.20882zbMATH Open1442.05008arXiv1506.02340OpenAlexW2965755394MaRDI QIDQ5113938FDOQ5113938

Authors: Charles Radin, Peter Winkler, Richard Kenyon, Daniel Král' 

Publication date: 19 June 2020

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We study scaling limits of random permutations ("permutons") constrained by having fixed densities of a finite number of patterns. We show that the limit shapes are determined by maximizing entropy over permutons with those constraints. In particular, we compute (exactly or numerically) the limit shapes with fixed hbox{12} density, with fixed hbox{12} and hbox{123} densities, with fixed hbox{12} density and the sum of hbox{123} and hbox{213} densities, and with fixed hbox{123} and hbox{321} densities. In the last case we explore a particular phase transition. To obtain our results, we also provide a description of permutons using a dynamic construction.

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

Recommendations

• The shape of random pattern-avoiding permutations
• Independence of permutation limits at infinitely many scales
• Scaling limits of permutation classes with a finite specification: a dichotomy
• Limits of permutation sequences
• On packing densities of permutations

zbMATH Keywords

permutation patternsgraphonspermutons

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cited In (24)

• The number of \(n\)-queens configurations
• Bounded affine permutations. II: Avoidance of decreasing patterns
• Expected patterns in permutation classes
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Asymptotics of discrete Schrödinger bridges via chaos decomposition
• Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
• Limit densities of patterns in permutation inflations
• Baxter permuton and Liouville quantum gravity
• A viewpoint for permutations with a low density of patterns
• On the cycle structure of Mallows permutations
• The feasible region for consecutive patterns of permutations is a cycle polytope
• Universal limits of substitution-closed permutation classes
• Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022
• Square permutations are typically rectangular
• Existence of a symmetric bipodal phase in the edge-triangle model
• Dense packing of patterns in a permutation
• Thresholds for patterns in random permutations with a given number of inversions
• The feasible region for consecutive patterns of permutations is a cycle polytope
• Permutation patterns and cell decompositions
• Independence of permutation limits at infinitely many scales
• Almost square permutations are typically square
• Density maximizers of layered permutations
• Patterns in random permutations
• The runsort permuton

This page was built for publication: Permutations with fixed pattern densities

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