Sciact
  • EN
  • RU

Singleton mesh patterns in multidimensional permutations Full article

Journal Journal of Combinatorial Theory. Series A
ISSN: 0097-3165 , E-ISSN: 1096-0899
Output data Year: 2024, Volume: 201, Article number : 105801, Pages count : 27 DOI: 10.1016/j.jcta.2023.105801
Tags Mesh pattern, Multidimensional permutation, Avoidability, Enumeration, Stirling numbers of the second kind
Authors Avgustinovich Sergey 1 , Kitaev Sergey 2 , Liese Jeffrey 3 , Potapov Vladimir 1 , Taranenko Anna 1
Affiliations
1 Sobolev Institute of Mathematics, Prospekt Akademika Koptyuga 4, Novosibirsk, 630090, Russia
2 Department of Mathematics and Statistics, University of Strathclyde, 26 Richmond Street, Glasgow G1, 1XH, United Kingdom. E
3 Department of Mathematics, California Polytechnic State University, San Luis Obispo, CA 93407, USA.

Funding (1)

1 Sobolev Institute of Mathematics FWNF-2022-0017

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.
Cite: Avgustinovich S. , Kitaev S. , Liese J. , Potapov V. , Taranenko A.
Singleton mesh patterns in multidimensional permutations
Journal of Combinatorial Theory. Series A. 2024. V.201. 105801 :1-27. DOI: 10.1016/j.jcta.2023.105801 WOS Scopus РИНЦ OpenAlex
Dates:
Submitted: Oct 6, 2022
Accepted: Aug 8, 2023
Published online: Aug 8, 2023
Published print: Apr 2, 2024
Identifiers:
Web of science: WOS:001077351500001
Scopus: 2-s2.0-85170291292
Elibrary: 64857199
OpenAlex: W4386549756
Citing:
DB Citing
Scopus 1
OpenAlex 1
Elibrary 1
Altmetrics: