Singleton mesh patterns in multidimensional permutations | Sciact - Система учета научной деятельности ИМ СО РАН

Singleton mesh patterns in multidimensional permutations Научная публикация

Журнал

Journal of Combinatorial Theory. Series A
ISSN: 0097-3165 , E-ISSN: 1096-0899

Вых. Данные

Год: 2024, Том: 201, Номер статьи : 105801, Страниц : 27 DOI: 10.1016/j.jcta.2023.105801

Ключевые слова

Mesh pattern, Multidimensional permutation, Avoidability, Enumeration, Stirling numbers of the second kind

Авторы

Avgustinovich Sergey ¹ , Kitaev Sergey ² , Liese Jeffrey ³ , Potapov Vladimir ¹ , Taranenko Anna ¹

Организации

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.

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0017

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

Поступила в редакцию:	6 окт. 2022 г.
Принята к публикации:	8 авг. 2023 г.
Опубликована online:	8 авг. 2023 г.
Опубликована в печати:	2 апр. 2024 г.

Web of science:	WOS:001077351500001
Scopus:	2-s2.0-85170291292
РИНЦ:	64857199
OpenAlex:	W4386549756

БД	Цитирований
Scopus	1
OpenAlex	1
РИНЦ	1