The feasible region for consecutive patterns of permutations is a cycle polytope
Algebraic Combinatorics, Volume 3 (2020) no. 6, pp. 1259-1281.

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 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, 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.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.135
Classification: 52B11,  05A05,  60C05
Keywords: Permutation patterns, cycle polytopes, overlap graphs.
Borga, Jacopo 1; Penaguiao, Raul 1

1 Institut für Mathematik Universität Zürich Winterthurerstr. 190 CH-8057 Zürich, Switzerland
@article{ALCO_2020__3_6_1259_0,
     author = {Borga, Jacopo and Penaguiao, Raul},
     title = {The feasible region for consecutive patterns of permutations is a cycle polytope},
     journal = {Algebraic Combinatorics},
     pages = {1259--1281},
     publisher = {MathOA foundation},
     volume = {3},
     number = {6},
     year = {2020},
     doi = {10.5802/alco.135},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.135/}
}
TY  - JOUR
TI  - The feasible region for consecutive patterns of permutations is a cycle polytope
JO  - Algebraic Combinatorics
PY  - 2020
DA  - 2020///
SP  - 1259
EP  - 1281
VL  - 3
IS  - 6
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.135/
UR  - https://doi.org/10.5802/alco.135
DO  - 10.5802/alco.135
LA  - en
ID  - ALCO_2020__3_6_1259_0
ER  - 
%0 Journal Article
%T The feasible region for consecutive patterns of permutations is a cycle polytope
%J Algebraic Combinatorics
%D 2020
%P 1259-1281
%V 3
%N 6
%I MathOA foundation
%U https://doi.org/10.5802/alco.135
%R 10.5802/alco.135
%G en
%F ALCO_2020__3_6_1259_0
Borga, Jacopo; Penaguiao, Raul. The feasible region for consecutive patterns of permutations is a cycle polytope. Algebraic Combinatorics, Volume 3 (2020) no. 6, pp. 1259-1281. doi : 10.5802/alco.135. https://alco.centre-mersenne.org/articles/10.5802/alco.135/

[1] Asplund, John; Fox, N. Bradley Enumerating cycles in the graph of overlapping permutations, Discrete Math., Volume 341 (2018) no. 2, pp. 427-438 | Article | MR: 3724110 | Zbl: 1376.05070

[2] Bassino, Frédérique; Bouvel, Mathilde; Féray, Valentin; Gerin, Lucas; Maazoun, Mickaël; Pierrot, Adeline Universal limits of substitution-closed permutation classes (2017) (https://arxiv.org/abs/1706.08333v1)

[3] Bassino, Frédérique; Bouvel, Mathilde; Féray, Valentin; Gerin, Lucas; Maazoun, Mickaël; Pierrot, Adeline Scaling limits of permutation classes with a finite specification: a dichotomy (2019) (https://arxiv.org/abs/1903.07522)

[4] Bassino, Frédérique; Bouvel, Mathilde; Féray, Valentin; Gerin, Lucas; Pierrot, Adeline The Brownian limit of separable permutations, Ann. Probab., Volume 46 (2018) no. 4, pp. 2134-2189 | Article | MR: 3813988 | Zbl: 1430.60013

[5] Bevan, David Permutations with few inversions are locally uniform (2019) (https://arxiv.org/abs/1908.07277)

[6] Borga, Jacopo Local convergence for permutations and local limits for uniform ρ-avoiding permutations with |ρ|=3, Probab. Theory Related Fields, Volume 176 (2020) no. 1-2, pp. 449-531 | Article | MR: 4055194 | Zbl: 1434.60035

[7] Borga, Jacopo; Bouvel, Mathilde; Féray, Valentin; Stufler, Benedikt A decorated tree approach to random permutations in substitution-closed classes, Electron. J. Probab., Volume 25 (2020), Paper no. 67, 52 pages | Article | MR: 4115736 | Zbl: 07225521

[8] Borga, Jacopo; Duchi, Enrica; Slivken, Erik Almost square permutations are typically square (2019) (https://arxiv.org/abs/1910.04813)

[9] Borga, Jacopo; Slivken, Erik Square permutations are typically rectangular (2019) https://arxiv.org/abs/1904.03080 (to appear in Annals of Applied Probability)

[10] Chung, Fan; Diaconis, Persi; Graham, Ron Universal cycles for combinatorial structures, Discrete Math., Volume 110 (1992) no. 1-3, pp. 43-59 | Article | MR: 1197444 | Zbl: 0776.05001

[11] Glebov, Roman; Hoppen, Carlos; Klimošová, Tereza; Kohayakawa, Yoshiharu; Král’, Daniel; Liu, Hong Densities in large permutations and parameter testing, European J. Combin., Volume 60 (2017), pp. 89-99 | Article | MR: 3567538 | Zbl: 1348.05010

[12] Gleiss, Petra M.; Leydold, Josef; Stadler, Peter F. Circuit bases of strongly connected digraphs, 2001 (Tech. report, Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business) | Zbl: 1055.05068

[13] Hoppen, Carlos; Kohayakawa, Yoshiharu; Moreira, Carlos Gustavo; Ráth, Balázs; Menezes Sampaio, Rudini Limits of permutation sequences, J. Combin. Theory Ser. B, Volume 103 (2013) no. 1, pp. 93-113 | Article | MR: 2995721 | Zbl: 1255.05174

[14] Huang, Hao; Linial, Nati; Naves, Humberto; Peled, Yuval; Sudakov, Benny On the 3-local profiles of graphs, J. Graph Theory, Volume 76 (2014) no. 3, pp. 236-248 | Article | MR: 3200287 | Zbl: 1305.05120

[15] Huang, Hao; Linial, Nati; Naves, Humberto; Peled, Yuval; Sudakov, Benny On the densities of cliques and independent sets in graphs, Combinatorica, Volume 36 (2016) no. 5, pp. 493-512 | Article | MR: 3572422 | Zbl: 1399.05125

[16] Johnson, J. Robert Universal cycles for permutations, Discrete Math., Volume 309 (2009) no. 17, pp. 5264-5270 | Article | MR: 2548540 | Zbl: 1181.05005

[17] Kenyon, Richard; Kráľ, Daniel; Radin, Charles; Winkler, Peter Permutations with fixed pattern densities, Random Structures Algorithms, Volume 56 (2020) no. 1, pp. 220-250 | Article | MR: 4052852 | Zbl: 1442.05008

[18] Kitaev, Sergey; Potapov, Vladimir N.; Vajnovszki, Vincent On shortening u-cycles and u-words for permutations, Discrete Appl. Math., Volume 260 (2019), pp. 203-213 | Article | MR: 3944621 | Zbl: 1409.05010

[19] Rahman, Mustazee; Virag, Balint; Vizer, Mate Geometry of permutation limits (2016) (https://arxiv.org/abs/1609.03891) | Zbl: 07134839

[20] Razborov, Alexander A. Flag algebras, J. Symbolic Logic, Volume 72 (2007) no. 4, pp. 1239-1282 | Article | MR: 2371204 | Zbl: 1146.03013

[21] Razborov, Alexander A. On the minimal density of triangles in graphs, Combin. Probab. Comput., Volume 17 (2008) no. 4, pp. 603-618 | Article | MR: 2433944 | Zbl: 1170.05036

[22] Romik, Dan Permutations with short monotone subsequences, Adv. in Appl. Math., Volume 37 (2006) no. 4, pp. 501-510 | Article | MR: 2266895 | Zbl: 1109.05015

[23] Starr, Shannon Thermodynamic limit for the Mallows model on S n , J. Math. Phys., Volume 50 (2009) no. 9, p. 095208, 15 | Article | MR: 2566888 | Zbl: 1241.82039

[24] Vargas, Yannic Hopf algebra of permutation pattern functions (2015) (https://hal.archives-ouvertes.fr/hal-01207565v1)

[25] Ziegler, Günter M. Lectures on polytopes, Graduate Texts in Mathematics, 152, Springer Science & Business Media, 2012 | Zbl: 0823.52002

Cited by Sources: