Séminaire Lotharingien de Combinatoire, 84B.30 (2020), 12 pp.
Jacopo Borga and Raúl Penaguiâo
The Feasible Region for Consecutive Patterns of Permutations is a Cycle Polytope
Abstract.
We study proportions of consecutive occurrences of permutations of a given size. 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. This allows us to compute the dimension, vertices and faces of the polytope.
Finally, we prove that the limits of classical occurrences and consecutive occurrences are independent, in some sense made precise in the extended abstract. As a consequence, the scaling limit of a sequence of permutations induces no constraints on the local limit and vice versa.
Received: November 20, 2019.
Accepted: February 20, 2020.
Final version: April 30, 2020.
The following versions are available: