Singleton mesh patterns in multidimensional permutations

DOI10.1016/J.JCTA.2023.105801MaRDI QIDQ6071953zbMATH OpenOpenAlexFDO

Authors Sergey Avgustinovich, Sergey Kitaev, Jeffrey Liese, Vladimir N. Potapov, Anna A. Taranenko

Publication date 29 November 2023

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

avoidabilityenumerationmesh patternmultidimensional permutationStirling numbers of the second kind

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Bell and Stirling numbers (11B73) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: This paper introduces the notion of mesh patterns in multidimensional permutations and initiates a systematic study of singleton mesh patterns (SMPs), which are multidimensional mesh patterns of length 1. A pattern is avoidable if there exist arbitrarily large permutations that do not contain it. As our main result, we give a complete characterization of avoidable SMPs using an invariant of a pattern that we call its rank. We show that determining avoidability for a $d$-dimensional SMP $P$ of cardinality $k$ is an $O(dcdotk)$ problem, while determining rank of $P$ is an NP-complete problem. Additionally, using the notion of a minus-antipodal pattern, we characterize SMPs which occur at most once in any $d$-dimensional permutation. Lastly, we provide a number of enumerative results regarding the distributions of certain general projective, plus-antipodal, minus-antipodal and hyperplane SMPs.

Recommendations

• On d-permutations and pattern avoidance classes
• Quadrant marked mesh patterns in 132-avoiding permutations
• scientific article; zbMATH DE number 7640030
• Quadrant marked mesh patterns in 132-avoiding permutations. II.
• Quadrant marked mesh patterns in 132-avoiding permutations. III.

Cites work

• Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings
• Distributions of mesh patterns of short lengths
• Enumeration of factorizable multi-dimensional permutations
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• Mesh patterns with superfluous mesh
• On multi-dimensional patterns
• Patterns in permutations and words.
• Quadrant marked mesh patterns in 123-avoiding permutations
• Quadrant marked mesh patterns in 132-avoiding permutations
• Quadrant marked mesh patterns in alternating permutations
• Reducibility among combinatorial problems
• Separable \(d\)-permutations and guillotine partitions
• Simple marked mesh patterns
• Wilf-classification of mesh patterns of short length

Cited in

(5)

• On d-permutations and pattern avoidance classes
• On a family of universal cycles for multi-dimensional permutations
• Joint equidistributions of mesh patterns 123 and 132 with minus antipodal shadings
• Patterns in multi-dimensional permutations
• On shortening universal words for multi-dimensional permutations

This page was built for publication: Singleton mesh patterns in multidimensional permutations

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