The feasible regions for consecutive patterns of pattern-avoiding permutations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914027945328640 |
|---|---|
| author | Borga, Jacopo Penaguiao, Raul |
| author_facet | Borga, Jacopo Penaguiao, Raul |
| contents | We study the feasible region for consecutive patterns of pattern-avoiding permutations. More precisely, given a family $\mathcal C$ of permutations avoiding a fixed set of patterns, we consider the limit of proportions of consecutive patterns on large permutations of $\mathcal C$. These limits form a region, which we call the consecutive patterns feasible region for $\mathcal C$.
We determine the dimension of the consecutive patterns feasible region for all families $\mathcal C$ closed either for the direct sum or the skew sum. These families include for instance the ones avoiding a single pattern and all substitution-closed classes. We further show that these regions are always convex and we conjecture that they are always polytopes. We prove this conjecture when $\mathcal C$ is the family of $τ$-avoiding permutations, with either $τ$ of size three or $τ$ a monotone pattern. Furthermore, in these cases we give a full description of the vertices of these polytopes via cycle polytopes.
Along the way, we discuss connections of this work with the problem of packing patterns in pattern-avoiding permutations and to the study of local limits for pattern-avoiding permutations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2010_06273 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | The feasible regions for consecutive patterns of pattern-avoiding permutations Borga, Jacopo Penaguiao, Raul Combinatorics Probability We study the feasible region for consecutive patterns of pattern-avoiding permutations. More precisely, given a family $\mathcal C$ of permutations avoiding a fixed set of patterns, we consider the limit of proportions of consecutive patterns on large permutations of $\mathcal C$. These limits form a region, which we call the consecutive patterns feasible region for $\mathcal C$. We determine the dimension of the consecutive patterns feasible region for all families $\mathcal C$ closed either for the direct sum or the skew sum. These families include for instance the ones avoiding a single pattern and all substitution-closed classes. We further show that these regions are always convex and we conjecture that they are always polytopes. We prove this conjecture when $\mathcal C$ is the family of $τ$-avoiding permutations, with either $τ$ of size three or $τ$ a monotone pattern. Furthermore, in these cases we give a full description of the vertices of these polytopes via cycle polytopes. Along the way, we discuss connections of this work with the problem of packing patterns in pattern-avoiding permutations and to the study of local limits for pattern-avoiding permutations. |
| title | The feasible regions for consecutive patterns of pattern-avoiding permutations |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2010.06273 |