On pattern-avoiding permutons
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 permut...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
29 January 2024
|
| In: |
Random structures & algorithms
Year: 2024, Volume: 65, Issue: 1, Pages: 46-60 |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.21208 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1002/rsa.21208 Verlag, lizenzpflichtig, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21208 
|
| Author Notes: | Frederik Garbe, Jan Hladký, Gábor Kun, Kristýna Pekárková |
| Summary: | 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)\ łeft(k-1\right) \ many, and this bound is sharp. We use this to give a simple proof of the “permutation removal lemma.” |
|---|---|
| Item Description: | Gesehen am 21.11.2024 |
| Physical Description: | Online Resource |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.21208 |