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: https://doi.org/10.5802/alco.135
Classification: 52B11,  05A05,  60C05
Keywords: Permutation patterns, cycle polytopes, overlap graphs.
@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/}
}
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