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)

01/07/2020

2020 Permutation Patterns Online Workshop.