Singleton mesh patterns in multidimensional permutations

Avgustinovich, Sergey and Kitaev, Sergey and Liese, Jeffrey and Potapov, Vladimir and Taranenko, Anna (2023) Singleton mesh patterns in multidimensional permutations. Journal of Combinatorial Theory. Series A. ISSN 0097-3165 (In Press)

[thumbnail of Avgustinovich-etal-JCTSA-2023-Singleton-mesh-patterns-in-multidimensional-permutations] Text. Filename: Avgustinovich_etal_JCTSA_2023_Singleton_mesh_patterns_in_multidimensional_permutations.pdf
Accepted Author Manuscript
Restricted to Repository staff only until 24 July 2024.
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (301kB) | Request a copy


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(d⋅k) 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.


Avgustinovich, Sergey, Kitaev, Sergey ORCID logoORCID:, Liese, Jeffrey, Potapov, Vladimir and Taranenko, Anna;