On pattern-avoiding permutons

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GARBE Frederik HLADKY Jan KUN Gabor PEKÁRKOVÁ Kristýna

Year of publication 2024
Type Article in Periodical
Magazine / Source Random Structures & Algorithms
MU Faculty or unit

Faculty of Informatics

Citation
web https://doi.org/10.1002/rsa.21208
Doi http://dx.doi.org/10.1002/rsa.21208
Keywords pattern-avoidance; permutations; permutons; removal lemma
Description The theory of limits of permutations leads to limit objects called permutons, which are certain Borel measures on the unit square. We prove that permutons avoiding a given permutation of order k$$ k $$ have a particularly simple structure. Namely, almost every fiber of the disintegration of the permuton (say, along the x-axis) consists only of atoms, at most (k-1)$$ left(k-1 ight) $$ many, and this bound is sharp. We use this to give a simple proof of the "permutation removal lemma."
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info