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.
Revised:
Accepted:
Published online:
Keywords: Permutation patterns, cycle polytopes, overlap graphs.
CC-BY 4.0
@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 AU - Borga, Jacopo AU - Penaguiao, Raul TI - The feasible region for consecutive patterns of permutations is a cycle polytope JO - Algebraic Combinatorics PY - 2020 SP - 1259 EP - 1281 VL - 3 IS - 6 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.135/ DO - 10.5802/alco.135 LA - en ID - ALCO_2020__3_6_1259_0 ER -
%0 Journal Article %A Borga, Jacopo %A Penaguiao, Raul %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://alco.centre-mersenne.org/articles/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] Enumerating cycles in the graph of overlapping permutations, Discrete Math., Volume 341 (2018) no. 2, pp. 427-438 | DOI | MR | Zbl
[2] Universal limits of substitution-closed permutation classes (2017) (https://arxiv.org/abs/1706.08333v1)
[3] Scaling limits of permutation classes with a finite specification: a dichotomy (2019) (https://arxiv.org/abs/1903.07522)
[4] The Brownian limit of separable permutations, Ann. Probab., Volume 46 (2018) no. 4, pp. 2134-2189 | DOI | MR | Zbl
[5] Permutations with few inversions are locally uniform (2019) (https://arxiv.org/abs/1908.07277)
[6] Local convergence for permutations and local limits for uniform -avoiding permutations with , Probab. Theory Related Fields, Volume 176 (2020) no. 1-2, pp. 449-531 | DOI | MR | Zbl
[7] A decorated tree approach to random permutations in substitution-closed classes, Electron. J. Probab., Volume 25 (2020), Paper no. 67, 52 pages | DOI | MR | Zbl
[8] Almost square permutations are typically square (2019) (https://arxiv.org/abs/1910.04813)
[9] Square permutations are typically rectangular (2019) https://arxiv.org/abs/1904.03080 (to appear in Annals of Applied Probability)
[10] Universal cycles for combinatorial structures, Discrete Math., Volume 110 (1992) no. 1-3, pp. 43-59 | DOI | MR | Zbl
[11] Densities in large permutations and parameter testing, European J. Combin., Volume 60 (2017), pp. 89-99 | DOI | MR | Zbl
[12] 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
[13] Limits of permutation sequences, J. Combin. Theory Ser. B, Volume 103 (2013) no. 1, pp. 93-113 | DOI | MR | Zbl
[14] On the 3-local profiles of graphs, J. Graph Theory, Volume 76 (2014) no. 3, pp. 236-248 | DOI | MR | Zbl
[15] On the densities of cliques and independent sets in graphs, Combinatorica, Volume 36 (2016) no. 5, pp. 493-512 | DOI | MR | Zbl
[16] Universal cycles for permutations, Discrete Math., Volume 309 (2009) no. 17, pp. 5264-5270 | DOI | MR | Zbl
[17] Permutations with fixed pattern densities, Random Structures Algorithms, Volume 56 (2020) no. 1, pp. 220-250 | DOI | MR | Zbl
[18] On shortening u-cycles and u-words for permutations, Discrete Appl. Math., Volume 260 (2019), pp. 203-213 | DOI | MR | Zbl
[19] Geometry of permutation limits (2016) (https://arxiv.org/abs/1609.03891) | Zbl
[20] Flag algebras, J. Symbolic Logic, Volume 72 (2007) no. 4, pp. 1239-1282 | DOI | MR | Zbl
[21] On the minimal density of triangles in graphs, Combin. Probab. Comput., Volume 17 (2008) no. 4, pp. 603-618 | DOI | MR | Zbl
[22] Permutations with short monotone subsequences, Adv. in Appl. Math., Volume 37 (2006) no. 4, pp. 501-510 | DOI | MR | Zbl
[23] Thermodynamic limit for the Mallows model on , J. Math. Phys., Volume 50 (2009) no. 9, p. 095208, 15 | DOI | MR | Zbl
[24] Hopf algebra of permutation pattern functions (2015) (https://hal.archives-ouvertes.fr/hal-01207565v1)
[25] Lectures on polytopes, Graduate Texts in Mathematics, 152, Springer Science & Business Media, 2012 | Zbl
Cited by Sources:
