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	https://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:	MUNI AWARD in Science and Humanitites 1