The feasible regions for consecutive patterns of pattern-avoiding permutations

DOI10.1016/J.DISC.2022.113219MaRDI QIDQ2099462zbMATH OpenOpenAlexFDO

Authors Jacopo Borga, Raul Penaguiao

Publication date 23 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2010.06273

zbMATH Keywords

consecutive patternscycle polytopesfeasible regionoverlap graphspattern-avoiding permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

Abstract: We study the feasible region for consecutive patterns of pattern-avoiding permutations. More precisely, given a family $mathcalC$ of permutations avoiding a fixed set of patterns, we consider the limit of proportions of consecutive patterns on large permutations of $mathcalC$. These limits form a region, which we call the consecutive patterns feasible region for $mathcalC$. We determine the dimension of the consecutive patterns feasible region for all families $mathcalC$ closed either for the direct sum or the skew sum. These families include for instance the ones avoiding a single pattern and all substitution-closed classes. We further show that these regions are always convex and we conjecture that they are always polytopes. We prove this conjecture when $mathcalC$ is the family of $au$-avoiding permutations, with either $au$ of size three or $au$ a monotone pattern. Furthermore, in these cases we give a full description of the vertices of these polytopes via cycle polytopes. Along the way, we discuss connections of this work with the problem of packing patterns in pattern-avoiding permutations and to the study of local limits for pattern-avoiding permutations.

Recommendations

• The feasible region for consecutive patterns of permutations is a cycle polytope
• The feasible region for consecutive patterns of permutations is a cycle polytope
• The shape of random pattern-avoiding permutations
• A probabilistic approach to consecutive pattern avoiding in permutations
• The most and the least avoided consecutive patterns

Cites work

• A decorated tree approach to random permutations in substitution-closed classes
• A singular mathematical promenade
• A survey of consecutive patterns in permutations
• An extension of Schensted's theorem
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels
• Bootstrap Percolation, the Schröder Numbers, and theN-Kings Problem
• Circuit bases of strongly connected digraphs
• Combinatorics of permutations
• Distributions of statistics over pattern-avoiding permutations
• Equipopularity classes in the separable permutations
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Independence of permutation limits at infinitely many scales
• Limits of permutation sequences
• Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
• Longest increasing subsequences in involutions avoiding patterns of length three
• Longest increasing subsequences in pattern-restricted permutations
• On packing densities of permutations
• Packing densities of patterns
• Pattern matching for permutations
• Patterns in random permutations avoiding some sets of multiple patterns
• Patterns in random permutations avoiding the pattern 132
• Patterns in random permutations avoiding the pattern 321
• Simple permutations and pattern restricted permutations
• The Brownian limit of separable permutations
• The feasible region for consecutive patterns of permutations is a cycle polytope
• Universal limits of substitution-closed permutation classes

Cited in

(7)

• A spectral approach to consecutive pattern-avoiding permutations
• The feasible region for consecutive patterns of permutations is a cycle polytope
• The feasible region for consecutive patterns of permutations is a cycle polytope
• An alternative proof for the expected number of distinct consecutive patterns in a random permutation
• An alternative proof for the expected number of distinct consecutive patterns in a random permutation
• The dimension of the feasible region of pattern densities (extended abstract)
• The dimension of the feasible region of pattern densities

This page was built for publication: The feasible regions for consecutive patterns of pattern-avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2099462)