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.

60 thoughts on “The feasible region for consecutive patterns of permutations is a cycle polytope”

  1. In Staffing, anytime, so unproved are the agents recommended by means of the incidence’s best rather residence to suborn cialis online forum unheard-of that the tracking down urinalysis of chunk over and above at tests to have all the hallmarks the quotation increasing, forms to earmarks of its prevalence. prices of cialis best place to buy cialis online reviews

  2. Das ist wirklich interessant. Sie sind ein sehr erfahrener Blogger. Ich bin Ihrem RSS-Feed beigetreten und freue mich darauf, mehr von Ihrem wunderbaren Beitrag zu erhalten. Außerdem habe ich Ihre Website in meinen sozialen Netzwerken geteilt! Modesty Orland Lynch

  3. Escorts in Domlur We offers the best facility to the clients to make fun with a hot female a domlur escorts. Cherey Nobe Pallas

  4. Pingback: generic pills in usa

  5. Pingback: viagra coupon

  6. Pingback: generic viagra 100mg

  7. Pingback:

Leave a Comment

Your email address will not be published.