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 limit of such proportions on large permutations forms a region, called \emph{feasible region}. We show that this feasible region is a polytope, more precisely the cycle polytope of a specific graph called \emph{overlap graph}. This allows us to compute the dimension, vertices and faces of the polytope, and to determine the equations that define it. Finally we prove that the limit of classical occurrences and consecutive occurrences are in some sense independent. As a consequence, the scaling limit of a sequence of permutations induces no constraints on the local limit and vice versa.

arXiv commentNew version including referee's corrections, accepted for publication in Algebraic Combinatorics

References in corpus (7)

• Thermodynamic Limit for the Mallows Model on $S_n$
• Connectivity and tree structure in finite graphs
• Universal limits of substitution-closed permutation classes
• Characterising planar Cayley graphs and Cayley complexes in terms of group presentations
• Almost square permutations are typically square
• Permutations with few inversions are locally uniform
• Scaling limits of permutation classes with a finite specification: a dichotomy

Cited by in corpus (8)

• Categorifications of rational Hilbert series and characters of $F{S}^{op}$ modules
• On the Okounkov-Olshanski formula for standard tableaux of skew shapes
• Quotients of skew morphisms of cyclic groups
• Basic Tetravalent Oriented Graphs of Independent-Cycle Type
• Resolutions of local face modules, functoriality, and vanishing of local $h$-vectors
• $2A$-Majorana Representations of $A_{12}$
• A note on projective dimension over twisted commutative algebras
• Compatible Recurrent Identities of the Sandpile Group and Maximal Stable Configurations