The feasible region for consecutive patterns of permutations is a cycle polytope

We study proportions of consecutive occurrences of permutation patterns of a given size \(k\). Specifically, the feasible limits of such proportions on large permutations form a region, called feasible region.

We show that this feasible region is a polytope, more precisely the cycle polytope of a specific graph called overlap graph. The latter is a labeled multi-graph defined as follows: the vertices are permutations of size \(k-1\) and for every permutation \(\pi\) of size \(k\) we draw an edge labeled by \(\pi\) from the pattern induced by the first \(k-1\) indices of \(\pi\) to the pattern induced by the last \(k-1\) indices of \(\pi\). The interpretation of the feasible region as a cycle polytope allows us to show that this is a \(k!-(k-1)!\) dimensional polytope. Moreover, we give several descriptions of the polytope: we classify all its vertices and facets, and furthermore give a combinatorial description of its faces. All these results are generalized for any cycle polytope of a given strongly connected graph.

In our work we further connect our combinatorial results with the study of permutation limits: Indeed, we show that the limits of classical occurrences and consecutive occurrences are independent in some (precise) sense, and as a consequence, we show that the permuton limit of a sequence of permutations induces no constraints on the local limit and vice versa.

We will also present some extensions of our work to pattern avoiding permutations: Specifically, we study the feasible region restricted to permutations on a given permutation class. In this framework, we show that, for all pattern \(\pi\) of size three, the feasible region of consecutive occurrences of \(\pi\)-avoiding permutations of a given size \(k\) is still a cycle polytope but its dimension is \(C_k-C_{k-1}\), where \(C_k\) is the \(k\)-th Catalan number.

Joint work with R. Penaguiao.

Poster (PDF)


2020 Permutation Patterns Online Workshop.

Leave a Comment

Your email address will not be published.