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...
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
29 January 2024
|
| In: |
Random structures & algorithms
Year: 2024, Jahrgang: 65, Heft: 1, Pages: 46-60 |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.21208 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1002/rsa.21208 Verlag, lizenzpflichtig, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.21208 
|
| Verfasserangaben: | Frederik Garbe, Jan Hladký, Gábor Kun, Kristýna Pekárková |
| Zusammenfassung: | 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.” |
|---|---|
| Beschreibung: | Gesehen am 21.11.2024 |
| Beschreibung: | Online Resource |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.21208 |