Permutations with fixed pattern densities

KENYON, Richard; Daniel KRÁĽ; Charles RADIN a Peter WINKLER. Permutations with fixed pattern densities. Random Structures and Algorithms. HOBOKEN: WILEY, 2020, roč. 56, č. 1, s. 220-250. ISSN 1042-9832. Dostupné z: https://doi.org/10.1002/rsa.20882.

Základní údaje

Originální název

Permutations with fixed pattern densities

Autoři

KENYON, Richard; Daniel KRÁĽ; Charles RADIN a Peter WINKLER

Vydání

Random Structures and Algorithms, HOBOKEN, WILEY, 2020, 1042-9832

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 1.131

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/20:00115548

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1002/rsa.20882

UT WoS

000479724400001

EID Scopus

2-s2.0-85071782068

Klíčová slova anglicky

graphons; permutation patterns; permutons

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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.