Singleton mesh patterns in multidimensional permutations

Avgustinovich, Sergey and Kitaev, Sergey and Liese, Jeffrey and Potapov, Vladimir and Taranenko, Anna (2024) Singleton mesh patterns in multidimensional permutations. Journal of Combinatorial Theory. Series A, 201 (C). 105801. ISSN 0097-3165 (https://doi.org/10.1016/j.jcta.2023.105801)

[thumbnail of Avgustinovich-etal-JCTSA-2023-Singleton-mesh-patterns-in-multidimensional-permutations]
Preview
 Text. Filename: Avgustinovich_etal_JCTSA_2023_Singleton_mesh_patterns_in_multidimensional_permutations.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (301kB)| Preview
[thumbnail of Singleton-mesh-patterns-in-multidimensional-permutations]
Preview
 Text. Filename: Singleton-mesh-patterns-in-multidimensional-permutations.pdf
Final Published Version
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (516kB)| Preview

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(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.

ORCID iDs

Avgustinovich, Sergey, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647, Liese, Jeffrey, Potapov, Vladimir and Taranenko, Anna;
CORE (COnnecting REpositories)