Séminaire Combinatoire et Théorie des Nombres ICJ

The feasible region for consecutive occurrences of large permutations

by Raúl Penaguiao (Université de Zurich)

Bât. Braconnier, salle Fokko du Cloux (ICJ, Université Lyon 1)

Bât. Braconnier, salle Fokko du Cloux

ICJ, Université Lyon 1


The study of patterns in permutations has steadily gathered interest in combinatorics.
The notion of classical pattern has been well studied so far, for instance giving rise to the limit object of a permuton.
The proportions of these patterns takes values between zero and one and the precise range for each pattern is well known.

The question thus arises for a family of patterns, if we can find permutations whose proportions of patterns match assigned values simultaneously for each pattern in the family.
This forms a feasible region, and the description of this feasible region in the context of classical patterns has had wide range of answers.
In this talk we will see how the feasible region in the context of consecutive patterns, a notion closely related to classical patterns, behaves much better.
Specifically, we will encode consecutive patterns as walks on a suitable graph, the overlap graph, and see that the feasible region is a polytope whose vertices correspond to cycles of the overlap graph. We finally give some insight on its face structure.