KENYON, Richard, Daniel KRÁĽ, Charles RADIN and Peter WINKLER. Permutations with fixed pattern densities. Random Structures and Algorithms. HOBOKEN: WILEY, 2020, vol. 56, No 1, p. 220-250. ISSN 1042-9832. Available from: https://dx.doi.org/10.1002/rsa.20882.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Permutations with fixed pattern densities
Authors KENYON, Richard, Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution), Charles RADIN and Peter WINKLER.
Edition Random Structures and Algorithms, HOBOKEN, WILEY, 2020, 1042-9832.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10200 1.2 Computer and information sciences
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
WWW URL
Impact factor Impact factor: 1.131
RIV identification code RIV/00216224:14330/20:00115548
Organization unit Faculty of Informatics
Doi http://dx.doi.org/10.1002/rsa.20882
UT WoS 000479724400001
Keywords in English graphons; permutation patterns; permutons
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 26/4/2021 08:25.
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 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.
PrintDisplayed: 1/8/2024 12:21