Informace o publikaci

Permutations with fixed pattern densities

Autoři

KENYON Richard KRÁĽ Daniel RADIN Charles WINKLER Peter

Rok publikování 2020
Druh Článek v odborném periodiku
Časopis / Zdroj RANDOM STRUCTURES & ALGORITHMS
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://dx.doi.org/10.1002/rsa.20882
Doi http://dx.doi.org/10.1002/rsa.20882
Klíčová slova graphons; permutation patterns; permutons
Popis 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 12 density, with fixed 12 and 123 densities, with fixed 12 density and the sum of 123 and 213 densities, and with fixed 123 and 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.