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

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;
  • Item type:Article
    ID code:86344
    Dates:
    Date
    Event
    24 July 2023
    Published
    24 July 2023
    Accepted
    Keywords:mesh pattern, multidimensional permutation, avoidability, enumeration, Stirling numbers of the second kind, Mathematics, Discrete Mathematics and Combinatorics
    Subjects:Science > Mathematics
    Department:Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:01 Aug 2023 14:12
    Last modified:01 Aug 2023 14:15
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/86344
CORE (COnnecting REpositories)