Permutations with fixed pattern densities

DOI10.1002/RSA.20882MaRDI QIDQ5113938zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

permutation patternsgraphonspermutons

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

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.

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

Cited in

(28)

• Patterns in random permutations
• The runsort permuton
• Bounded affine permutations. II: Avoidance of decreasing patterns
• The number of \(n\)-queens configurations
• Limits of permutation sequences
• Expected patterns in permutation classes
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
• Asymptotics of discrete Schrödinger bridges via chaos decomposition
• Limit densities of patterns in permutation inflations
• Baxter permuton and Liouville quantum gravity
• On the cycle structure of Mallows permutations
• A viewpoint for permutations with a low density of patterns
• Universal limits of substitution-closed permutation classes
• The feasible region for consecutive patterns of permutations is a cycle polytope
• Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022
• Square permutations are typically rectangular
• Scaling limits of permutation classes with a finite specification: a dichotomy
• 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
• Permutation patterns and cell decompositions
• The feasible region for consecutive patterns of permutations is a cycle polytope
• On pattern-avoiding permutons
• Independence of permutation limits at infinitely many scales
• A decorated tree approach to random permutations in substitution-closed classes
• Almost square permutations are typically square
• Density maximizers of layered permutations

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)