The feasible regions for consecutive patterns of pattern-avoiding permutations

Jacopo Borga, Raul Penaguiao

Published 2020-10-13Version 1

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 study the limit of proportions of consecutive patterns on large permutations of $\mathcal C$. These limits form a region, which we call the \emph{pattern-avoiding feasible region for $\mathcal C$}. We show that, when $\mathcal C$ is the family of $\tau$-avoiding permutations, with either $\tau$ of size three or $\tau$ a monotone pattern, the pattern-avoiding feasible region for $\mathcal C$ is a polytope. We also determine its dimension using a new tool for the monotone pattern case whereby we are able to compute the dimension of the image of a polytope after a projection. We further show some general results for the pattern-avoiding feasible region for any family $\mathcal C$ of permutations avoiding a fixed set of patterns, and we conjecture a general formula for its dimension. 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.